堆定義
堆實際上是一棵完全二叉樹，其任何一非葉節點滿足性質：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]（小頂堆）或者：Key[i]>=Key[2i+1]&&key>=key[2i+2]（大頂堆）
即任何一非葉節點的關鍵字不大于或者不小于其左右孩子節點的關鍵字。
堆排序的思想
利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。
這里以最大堆為基礎，其基本思想為：
1.將初始待排序關鍵字序列(R1,R2....Rn)構建成大頂堆，此堆為初始的無序區；
2.將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,......Rn-1)和新的有序區(Rn),且滿足R[1,2...n-1]<=R[n];
3.由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,......Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2....Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。
C語言實現
1.基于最大堆實現升序排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
// 初始化堆void initHeap(int a[], int len) { // 從完全二叉樹最后一個非子節點開始 // 在數組中第一個元素的索引是0 // 第n個元素的左孩子為2n+1，右孩子為2n+2， // 最后一個非子節點位置在(n - 1) / 2 for (int i = (len - 1) / 2; i >= 0; --i) { adjustMaxHeap(a, len, i); }} void adjustMaxHeap(int a[], int len, int parentNodeIndex) { // 若只有一個元素，那么只能是堆頂元素，也沒有必要再排序了 if (len <= 1) { return; } // 記錄比父節點大的左孩子或者右孩子的索引 int targetIndex = -1; // 獲取左、右孩子的索引 int leftChildIndex = 2 * parentNodeIndex + 1; int rightChildIndex = 2 * parentNodeIndex + 2; // 沒有左孩子 if (leftChildIndex >= len) { return; } // 有左孩子，但是沒有右孩子 if (rightChildIndex >= len) { targetIndex = leftChildIndex; } // 有左孩子和右孩子 else { // 取左、右孩子兩者中最大的一個 targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex; } // 只有孩子比父節點的值還要大，才需要交換 if (a[targetIndex] > a[parentNodeIndex]) { int temp = a[targetIndex]; a[targetIndex] = a[parentNodeIndex]; a[parentNodeIndex] = temp; // 交換完成后，有可能會導致a[targetIndex]結點所形成的子樹不滿足堆的條件， // 若不滿足堆的條件，則調整之使之也成為堆 adjustMaxHeap(a, len, targetIndex); }} void heapSort(int a[], int len) { if (len <= 1) { return; } // 初始堆成無序最大堆 initHeap(a, len); for (int i = len - 1; i > 0; --i) { // 將當前堆頂元素與最后一個元素交換，保證這一趟所查找到的堆頂元素與最后一個元素交換 // 注意：這里所說的最后不是a[len - 1]，而是每一趟的范圍中最后一個元素 // 為什么要加上>0判斷？每次不是說堆頂一定是最大值嗎？沒錯，每一趟調整后，堆頂是最大值的 // 但是，由于len的范圍不斷地縮小，導致某些特殊的序列出現異常 // 比如說，5, 3, 8, 6, 4序列，當調整i=1時，已經調整為3,4,5,6,8序列，已經有序了 // 但是導致了a[i]與a[0]交換，由于變成了4,3,5,6,8反而變成無序了! if (a[0] > a[i]) { int temp = a[0]; a[0] = a[i]; a[i] = temp; } // 范圍變成為： // 0...len-1 // 0...len-1-1 // 0...1 // 結束 // 其中，0是堆頂，每次都是找出在指定的范圍內比堆頂還大的元素，然后與堆頂元素交換 adjustMaxHeap(a, i - 1, 0); }} |
2.基于最小堆實現降序排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
// 初始化堆void initHeap(int a[], int len) { // 從完全二叉樹最后一個非子節點開始 // 在數組中第一個元素的索引是0 // 第n個元素的左孩子為2n+1，右孩子為2n+2， // 最后一個非子節點位置在(n - 1) / 2 for (int i = (len - 1) / 2; i >= 0; --i) { adjustMinHeap(a, len, i); }} void adjustMinHeap(int a[], int len, int parentNodeIndex) { // 若只有一個元素，那么只能是堆頂元素，也沒有必要再排序了 if (len <= 1) { return; } // 記錄比父節點大的左孩子或者右孩子的索引 int targetIndex = -1; // 獲取左、右孩子的索引 int leftChildIndex = 2 * parentNodeIndex + 1; int rightChildIndex = 2 * parentNodeIndex + 2; // 沒有左孩子 if (leftChildIndex >= len) { return; } // 有左孩子，但是沒有右孩子 if (rightChildIndex >= len) { targetIndex = leftChildIndex; } // 有左孩子和右孩子 else { // 取左、右孩子兩者中最上的一個 targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex; } // 只有孩子比父節點的值還要小，才需要交換 if (a[targetIndex] < a[parentNodeIndex]) { int temp = a[targetIndex]; a[targetIndex] = a[parentNodeIndex]; a[parentNodeIndex] = temp; // 交換完成后，有可能會導致a[targetIndex]結點所形成的子樹不滿足堆的條件， // 若不滿足堆的條件，則調整之使之也成為堆 adjustMinHeap(a, len, targetIndex); }} void heapSort(int a[], int len) { if (len <= 1) { return; } // 初始堆成無序最小堆 initHeap(a, len); for (int i = len - 1; i > 0; --i) { // 將當前堆頂元素與最后一個元素交換，保證這一趟所查找到的堆頂元素與最后一個元素交換 // 注意：這里所說的最后不是a[len - 1]，而是每一趟的范圍中最后一個元素 // 為什么要加上>0判斷？每次不是說堆頂一定是最小值嗎？沒錯，每一趟調整后，堆頂是最小值的 // 但是，由于len的范圍不斷地縮小，導致某些特殊的序列出現異常 // 比如說，5, 3, 8, 6, 4序列，當調整i=1時，已經調整為3,4,5,6,8序列，已經有序了 // 但是導致了a[i]與a[0]交換，由于變成了4,3,5,6,8反而變成無序了! if (a[0] < a[i]) { int temp = a[0]; a[0] = a[i]; a[i] = temp; } // 范圍變成為： // 0...len-1 // 0...len-1-1 // 0...1 // 結束 // 其中，0是堆頂，每次都是找出在指定的范圍內比堆頂還小的元素，然后與堆頂元素交換 adjustMinHeap(a, i - 1, 0); }} |
3.C語言版測試
大家可以測試一下：
|
1
2
3
4
5
6
7
|
// int a[] = {5, 3, 8, 6, 4};int a[] = {89,-7,999,-89,7,0,-888,7,-7};heapSort(a, sizeof(a) / sizeof(int)); for (int i = 0; i < sizeof(a) / sizeof(int); ++i) { NSLog(@"%d", a[i]);} |
