堆是一棵完全二叉树，其任一非叶结点的关键字不小于（最大堆而言）或不大于（最小堆而言）其左右孩子节点的关键字。
假设待排序数组为A[]，那么初始的话我们可以按层次编号建树，对结点i（从零开始）而言，其左右结点分别为2*i+1、2*i+2。
堆排序的算法可大致描述如下：
1.建立最大堆（或最小堆）；
2.
for(i = heapSize -1; i > 0; i --) { swap(A[i], A[0]); heapSize --; RestoreHeap(A, 0); }
堆排序整体代码如下：
1 #include <iostream> 2 #include <cstdlib> 3 using namespace std; 4 int heapSize; 5 void swap(int &a, int &b) 6 { 7 int temp = a; 8 a = b; 9 b = temp; 10 } 11 void RestoreHeap(int *A, int i) 12 { 13 int l = 2*i + 1; 14 int r = 2*i + 2; 15 int great; 16 if(l < heapSize && A[l] > A[i]) 17 great = l; 18 else 19 great = i; 20 if(r < heapSize && A[r] > A[great]) 21 great = r; 22 if (great != i) 23 { 24 swap(A[i], A[great]); 25 RestoreHeap(A, great); 26 } 27 } 28 //非递归Restore算法 29 void Restore(int *A, int i) 30 { 31 int j = i; 32 int l, r, great; 33 while(j <= heapSize/2 - 1) 34 { 35 l = 2*j + 1; 36 r = 2*j + 2; 37 if(r < heapSize && A[l] < A[r]) 38 great = r; 39 else 40 great = l; 41 if(A[great] > A[j]) 42 { 43 swap(A[great], A[j]); 44 j = great; 45 } 46 else 47 break; 48 } 49 } 50 void BuildMaxHeap(int *A) 51 { 52 for(int i = heapSize/2 - 1; i >= 0; i--) 53 //RestoreHeap(A, i); 54 Restore(A, i); 55 } 56 void HeapSort(int *A) 57 { 58 BuildMaxHeap(A); 59 for(int i = heapSize - 1; i > 0; i--) 60 { 61 swap(A[i], A[0]); 62 heapSize --; 63 //RestoreHeap(A, 0); 64 Restore(A, 0); 65 } 66 } 67 int main() 68 { 69 int *A = NULL; 70 cout<<"Input heap size and its values:"<<endl; 71 while(cin>>heapSize && heapSize) 72 { 73 try 74 { 75 A = new int[heapSize]; 76 } 77 catch(const bad_alloc &e) 78 { 79 cerr<<"bad alloc error:"<<e.what()<<endl; 80 abort(); 81 } 82 int i; 83 for(i = 0; i < heapSize; i++) 84 { 85 cin>>A[i]; 86 } 87 int size = heapSize; 88 HeapSort(A); 89 cout<<"After sort:"<<endl; 90 for(i = 0; i < size; i++) 91 cout<<A[i]<<" "; 92 cout<<endl<<"Input heap size and its values:"<<endl; 93 delete A; 94 A = NULL; 95 } 96 return 0; 97 }
堆排序是不稳定的排序，因为在重建堆的时候并没有考虑原来的顺序，即便关键字相同的元素也有可能进行交换。