堆排序算法
开始时，堆排序算法先用BuildMaxHeap 将输入数组data[0...n-1]构造成一个最大堆。因为数组中最大元素在根data[0]，则可以通过把它与data[n-1]互换来达到最终正确的位置。但是新的根元素可能违背了最大堆性质。这时调用MaxHeapify(data,0,size)就可以保持这一性质，在data[0...n-2]中构造出最大堆。对排序算法不断重复这个过程，堆的大小由n-1
一直降到 2，排序完毕。
//Heap Sort
//by yew1eb
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000
/*
*堆化
*MaxHeapify让a[i]在堆中"下降"，使以i为根的子树保持堆的性质。
*/
void MaxHeapify(int *data, int i, const int size) {
int p = i*2 + 1;
while ( p<size ) {
if( p+1<size ) {
if( data[p]>data[p+1] )
++p;
}
if(data[i]>data[p] ) {
swap(data[p], data[i]);
i = p;
p =i*2 + 1;
} else
break;
}
}
void BuildMaxHeap(int *data, int size) {
for(int i=size/2; i>=0; --i)
MaxHeapify(data, i, size);
}
void HeapSort(int *data, int size) {
BuildMaxHeap(data,size);
for(int i = size -1; i>0; --i) {
swap(data[0], data[i]);
MaxHeapify(data,0,i);
}
}
void PrintArray(int *data, int size) {
for(int i=0; i<size; ++i)
cout<<data[i]<<" ";
cout<<endl;
}
int main() {
int size;
int data[N];
cin>>size;
for(int i=0; i<size; ++i)
cin>>data[i];
HeapSort(data,size);
PrintArray(data,size);
return 0;
}