[cpp]
/***********************************************************************************
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。
堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：
即子結點的鍵值或索引總是小於（或者大於）它的父節點。
通常堆是通過一維數組來實現的。在起始數組為 0 的情形中：
父節點i的左子節點在位置 (2*i+1);
父節點i的右子節點在位置 (2*i+2);
子節點i的父節點在位置 floor((i-1)/2);
堆的操作
在堆的數據結構中，堆中的最大值總是位於根節點。堆中定義以下幾種操作：
最大堆調整（Min_Heapify）：將堆的末端子結點作調整，使得子結點永遠小於父結點
創建最大堆（Build_Min_Heap）：將堆所有數據重新排序
注：堆排序不是一種穩定排序。
用小根堆得辦法尋找最大的K個數
用容量為K的最小堆來存儲最大的K個數。最小堆的堆頂元素就是最大K個數中的最小的一個。
每次掃描一個數據X，如果X比堆頂元素Y小，則不需要改變原來的堆。如果X比堆頂元素大，
那麼用X替換堆頂元素Y，在替換之後，X可能破壞了最小堆的結構，需要調整堆來維持堆的性質。
調整過程時間復雜度為O(logK)。 全部的時間復雜度為O(N*logK)。
這種方法當數據量比較大的時候，比較方便。因為對所有的數據只會遍歷一次，
*************************************************************************************/
#include <cmath>
#include<cstdlib>
#include<time.h>
#include<cstdio>
#include<iostream>
using namespace std;
//產生隨機數組
void Random(int a[],int n)
{
int i=0;
srand( (unsigned)time( NULL ) );
while(i<n)
{
a[i++]=rand()/999;
}
}
void print(int a[], int len)
{
int i;
for (i = 0; i < len; i++)
printf("%6d ", a[i]);
printf("\n");
}
int parent(int);
int left(int);
int right(int);
void Min_Heapify(int [], int, int);
void Build_Min_Heap(int A[],int size);
void HeapSort(int [], int);
/*求父親*/
int parent(int i)
{
return (int)floor((i - 1) / 2);
}
/*求左孩子*/
int left(int i)
{
return (2 * i + 1);
}
/*求右孩子*/
int right(int i)
{
return (2 * i + 2);
}
/*調整堆使其滿足堆得性質*/
void Min_Heapify(int A[], int i, int heap_size)
{
int l = left(i);
int r = right(i);
int least;
int temp;
/*找到父親 左孩子 右孩子 之間的最大值*/
if(l < heap_size && A[l] < A[i])
{
least = l;
}
else
{
least = i;
}
if(r < heap_size && A[r] < A[least])
{
least = r;
}
/*如果父親不是最大的，則把父親和兩個孩子的較大值交換*/
if(least != i)
{
temp = A[i];
A[i] = A[least];
A[least] = temp;
/*交換之後破壞了較大孩子的堆得性質，對其進行調整*/
Min_Heapify(A, least, heap_size);
}
}
/*簡歷大頂堆*/
void Build_Min_Heap(int A[],int size)
{
/* 因為數組A[0]要存放數據 所以左孩子為2*i+1 右孩子為 2*i+2 */
/*取最後一個飛葉子節點 即堆頂 根節點
0 1 2 ->mid=1=3/2 n/2
0 1 2 3 ->mid=2=4/2 n/2
0 1 2 3 4 ->mid=2=5/2 n/2
0 1 2 3 4 5 ->mid=3=6/2 n/2 取中間元素偏右的為根節點使其成為完全二叉樹
*/
int begin = size/2 ; // 堆頂元素
for(int i = begin; i >= 0; i--)
{
Min_Heapify(A, i, size);
}
}
/*堆排序開始*/
void HeapSort(int A[], int heap_size)
{
Build_Min_Heap(A,heap_size);
//建立大頂堆之後 堆頂已經是所有元素中最大的了
int temp;
//a[0]是數組的第一個元素 a[heap_size - 1]是數組的最後一個元素
/*將堆頂依次和最後一個葉子節點交換*/
for(int i = heap_size - 1; i >= 0; i--)
{
temp = A[0];
A[0] = A[i];
A[i] = temp;
//交換之後破壞了堆得性質 重新調整
Min_Heapify(A, 0, i); //i 是元素個數 每交換依次元素就少一個
}
}
void TopK(int arr[],int n,int K)
{
if(n<K)
{
cout<<"error"<<endl;
return;
}
int *heap=new int[K];
//隨機將前K個數裝入數組構建小頂堆
for(int i=0;i<K;i++)
{
heap[i]=arr[i];
}
Build_Min_Heap(heap,K);//建立最小堆
//從生下的數中找比小頂堆堆頂大的數並與堆頂交換(直接放在堆頂位置不交換效率更高)
for(int i=K;i<n;i++)
{
if(arr[i]>heap[0])
{
heap[0]=arr[i];
//破壞了最小對的性質 對最小對進行調整
Min_Heapify(heap,0,K);
}
}
for(int i=0;i<K;i++)
cout<<heap[i]<<' ';
delete []heap;
}
int main()
{
int a[30] = {0};
Random(a,30);
print(a,30);
cout<<endl<<"------------------------------------"<<endl;
TopK(a,30,5);
cout<<endl<<"------------------------------------"<<endl;
HeapSort(a,30);
cout<<endl<<"-----------------------------------"<<endl;
print(a,30);
return 0;
}
/******************
21 0 7 26 10 11 23 10 4
1 23 3 10 25 31 31 17 28
11 31 27 23 19 7 19 21 20
6 18 14
------------------------------------
27 28 31 31 31
------------------------------------
-----------------------------------
31 31 31 28 27 26 25 23 23
23 21 21 20 19 19 18 17 14
11 11 10 10 10 7 7 6 4
3 1 0
Process returned 0 (0x0) execution time : 0.030 s
Press any key to continue.
*******************/
/***********************************************************************************
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。
堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：
即子結點的鍵值或索引總是小於（或者大於）它的父節點。
通常堆是通過一維數組來實現的。在起始數組為 0 的情形中：
父節點i的左子節點在位置 (2*i+1);
父節點i的右子節點在位置 (2*i+2);
子節點i的父節點在位置 floor((i-1)/2);
堆的操作
在堆的數據結構中，堆中的最大值總是位於根節點。堆中定義以下幾種操作：
最大堆調整（Min_Heapify）：將堆的末端子結點作調整，使得子結點永遠小於父結點
創建最大堆（Build_Min_Heap）：將堆所有數據重新排序
注：堆排序不是一種穩定排序。
用小根堆得辦法尋找最大的K個數
用容量為K的最小堆來存儲最大的K個數。最小堆的堆頂元素就是最大K個數中的最小的一個。
每次掃描一個數據X，如果X比堆頂元素Y小，則不需要改變原來的堆。如果X比堆頂元素大，
那麼用X替換堆頂元素Y，在替換之後，X可能破壞了最小堆的結構，需要調整堆來維持堆的性質。
調整過程時間復雜度為O(logK)。 全部的時間復雜度為O(N*logK)。
這種方法當數據量比較大的時候，比較方便。因為對所有的數據只會遍歷一次，
*************************************************************************************/
#include <cmath>
#include<cstdlib>
#include<time.h>
#include<cstdio>
#include<iostream>
using namespace std;
//產生隨機數組
void Random(int a[],int n)
{
int i=0;
srand( (unsigned)time( NULL ) );
while(i<n)
{
a[i++]=rand()/999;
}
}
void print(int a[], int len)
{
int i;
for (i = 0; i < len; i++)
printf("%6d ", a[i]);
printf("\n");
}
int parent(int);
int left(int);
int right(int);
void Min_Heapify(int [], int, int);
void Build_Min_Heap(int A[],int size);
void HeapSort(int [], int);
/*求父親*/
int parent(int i)
{
return (int)floor((i - 1) / 2);
}
/*求左孩子*/
int left(int i)
{
return (2 * i + 1);
}
/*求右孩子*/
int right(int i)
{
return (2 * i + 2);
}
/*調整堆使其滿足堆得性質*/
void Min_Heapify(int A[], int i, int heap_size)
{
int l = left(i);
int r = right(i);
int least;
int temp;
/*找到父親 左孩子 右孩子 之間的最大值*/
if(l < heap_size && A[l] < A[i])
{
least = l;
}
else
{
least = i;
}
if(r < heap_size && A[r] < A[least])
{
least = r;
}
/*如果父親不是最大的，則把父親和兩個孩子的較大值交換*/
if(least != i)
{
temp = A[i];
A[i] = A[least];
A[least] = temp;
/*交換之後破壞了較大孩子的堆得性質，對其進行調整*/
Min_Heapify(A, least, heap_size);
}
}
/*簡歷大頂堆*/
void Build_Min_Heap(int A[],int size)
{
/* 因為數組A[0]要存放數據 所以左孩子為2*i+1 右孩子為 2*i+2 */
/*取最後一個飛葉子節點 即堆頂 根節點
0 1 2 ->mid=1=3/2 n/2
0 1 2 3 ->mid=2=4/2 n/2
0 1 2 3 4 ->mid=2=5/2 n/2
0 1 2 3 4 5 ->mid=3=6/2 n/2 取中間元素偏右的為根節點使其成為完全二叉樹
*/
int begin = size/2 ; // 堆頂元素
for(int i = begin; i >= 0; i--)
{
Min_Heapify(A, i, size);
}
}
/*堆排序開始*/
void HeapSort(int A[], int heap_size)
{
Build_Min_Heap(A,heap_size);
//建立大頂堆之後 堆頂已經是所有元素中最大的了
int temp;
//a[0]是數組的第一個元素 a[heap_size - 1]是數組的最後一個元素
/*將堆頂依次和最後一個葉子節點交換*/
for(int i = heap_size - 1; i >= 0; i--)
{
temp = A[0];
A[0] = A[i];
A[i] = temp;
//交換之後破壞了堆得性質 重新調整
Min_Heapify(A, 0, i); //i 是元素個數 每交換依次元素就少一個
}
}
void TopK(int arr[],int n,int K)
{
if(n<K)
{
cout<<"error"<<endl;
return;
}
int *heap=new int[K];
//隨機將前K個數裝入數組構建小頂堆
for(int i=0;i<K;i++)
{
heap[i]=arr[i];
}
Build_Min_Heap(heap,K);//建立最小堆
//從生下的數中找比小頂堆堆頂大的數並與堆頂交換(直接放在堆頂位置不交換效率更高)
for(int i=K;i<n;i++)
{
if(arr[i]>heap[0])
{
heap[0]=arr[i];
//破壞了最小對的性質 對最小對進行調整
Min_Heapify(heap,0,K);
}
}
for(int i=0;i<K;i++)
cout<<heap[i]<<' ';
delete []heap;
}
int main()
{
int a[30] = {0};
Random(a,30);
print(a,30);
cout<<endl<<"------------------------------------"<<endl;
TopK(a,30,5);
cout<<endl<<"------------------------------------"<<endl;
HeapSort(a,30);
cout<<endl<<"-----------------------------------"<<endl;
print(a,30);
return 0;
}
/******************
21 0 7 26 10 11 23 10 4
1 23 3 10 25 31 31 17 28
11 31 27 23 19 7 19 21 20
6 18 14
------------------------------------
27 28 31 31 31
------------------------------------
-----------------------------------
31 31 31 28 27 26 25 23 23
23 21 21 20 19 19 18 17 14
11 11 10 10 10 7 7 6 4
3 1 0
Process returned 0 (0x0) execution time : 0.030 s
Press any key to continue.
*******************/
