堆的意思就是上面的都比下面大，或者小。
舉個例子，下圖就是個最小堆，父節點都比子節點小。如果將其反過來，父節點都比子節點大，那就是最大堆。
如圖，想象一下東西是怎麼磊成堆的，就能理解這個名字的精妙了。
1
/
2 7
/ /
3 4 8 9
堆很容易就可以用數組表示，任意元素i，其子節點就是[2*i]，[2*i+1]，其父節點就是[j/2]，寫起來很簡單吧，也很容易理解。
堆排序的思想就是利用堆的這種父子節點大小關系的特性，來降低比較次數。
想象一下單循環淘汰賽，比如說歐洲冠軍杯。先捉對厮殺，再一層一層往上走。堆排序就是這麼做的。第一次從N中選出冠軍。然後將冠軍拿掉，剩下的N-1再選，以此計算，直到剩最後一個時，全部排序也就完成了。
舉個例子：數組為：2, 5, 3, 2, 3, 0, 8, 1
得到初始狀態如下圖：
2
/
5 3
/ /
2 3 0 8
/
1
選出第一個冠軍：
8
/
5 2
/ /
2 3 0 3
/
1
將冠軍移到最後，然後，圖也就變成
1
/
5 2
/ /
2 3 0 3
8
繼續選冠軍：
5
/
1 3
/ /
2 3 0 2
8
再將冠軍移到樹的最後：
2
/
1 3
/ /
2 3 0 5
8
繼續選冠軍：
3
/
2 3
/ /
2 1 0 5
8
再將冠軍移到樹的最後：
0
/
2 3
/
2 1 3 5
8
繼續選冠軍：
3
/
2 0
/
2 1 3 5
8
再將冠軍移到樹的最後：
1
/
2 0
/
2 3 3 5
8
繼續選冠軍：
2
/
1 0
/
2 3 3 5
8
再將冠軍移到樹的最後：
2
/
1 0
2 3 3 5
8
繼續選冠軍：
2
/
1 0
2 3 3 5
8
再將冠軍移到樹的最後：
0
/
1 2
2 3 3 5
8
繼續選冠軍：
1
/
0 2
2 3 3 5
8
再將冠軍移到樹的最後：
0
1 2
2 3 3 5
8
搞定啦！
0, 1, 2, 3, 3, 5, 8
代碼如下：
view plaincopy to clipboardprint?
void FindMaxInHeap(int arr[], const int size) {
for (int j = size - 1; j > 0; --j) {
int parent = j / 2;
int child = j;
if (j < size - 1 && arr[j] < arr[j+1]) {
++child;
}
if (arr[child] > arr[parent]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
}
}
}
void HeapSort(int arr[], const int size) {
for (int j = size; j > 0; --j) {
FindMaxInHeap(arr, j);
int tmp = arr[0];
arr[0] = arr[j - 1];
arr[j - 1] = tmp;
}
}
void TestHeapSort() {
int arr[] = {2, 5, 3, 2, 3, 0, 8, 1};
int n = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, n);
for (int j = 0; j < n; ++j) {
cout << arr[j] << ", ";
}
cout << endl;
}
