可以说堆排序兼具了插入排序和归并排序的优点。想插入排序一样，它sorts in place；同时时间复杂度达到归并排序的级别O(nlgn)。
以大根堆为例，大根堆中，除了根以外的每个结点i，都有: A[parent(i)]>=A[i]。
大根堆的基本过程包括：
- max_heapify(a,i).对结点i及其子孙结点保持大根堆的性质；
- build_max_heap.对给定的数组建堆。思路是从最后一个非叶子结点开始max_heapify；
- heapsort.进行大根堆排序.从最后一个元素开始，交换根结点和其位置，然后max_heapify后重复此过程。
//realization of heatsort
//the first element of the heap is a[1]
#include <iostream>
using namespace std;
inline int parent(int i)
{
return i/2;
}
inline int left(int i)
{
return 2*i;
}
inline int right(int i)
{
return 2*i+1;
}
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void max_heapify(int *a, int i,int heapsize);
void build_max_heap(int *a,int length);
void heapsort(int *a,int length);
int main()
{
int a[] = {0,2,12,54,6,57,81,23,456,4,1,1,56};//the 1st element
//is not included in heaps
int length = sizeof(a)/sizeof(int);
int i;
for(i=1;i<length;++i)
cout<<a[i]<<(i%10==9?'\n':' ');
build_max_heap(a,length-1);
heapsort(a,length-1);
cout<<"\nafter heapsort: \n";
for(i=1;i<length;++i)
cout<<a[i]<<(i%10==9?'\n':' ');
}
void max_heapify(int *a,int i,int heapsize)
{
int l = left(i) ;
int r = right(i);
int largest;
if(l<=heapsize && a[l] > a[i])
largest = l;
else
largest = i;
if(r<=heapsize && a[r] > a[largest])
largest = r;
if(largest != i)
{
swap(a[i],a[largest]);
max_heapify(a,largest,heapsize);
}
}
void build_max_heap(int *a, int length)
{
int notleaves = length/2;
int i;
for(i=notleaves;i>0;i--)
max_heapify(a,i,length);
}
void heapsort(int *a, int length)
{
int i;
build_max_heap(a,length);
for(i=length;i>1;i--)
{
swap(a[1],a[length]);
length = length - 1;
max_heapify(a,1,length);
}
}