堆排序(Heapsort)是指利用堆這種資料結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特 點快速定位指定索引的元素.
堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
- 大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；
- 小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；
堆排序的平均時間複雜度為 Ο(nlogn)
(選擇排序工作原理 - 第一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置， 然後再從剩餘的未排序元素中尋找到最小（大）元素，然後放到已排序的序列的末尾。以此類推，直到全部待 排序的資料元素的個數為零)
1. 排序核心實作
2. 算法步驟
- 建立一個堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互換；
- 把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端資料調整到相應位置；
- 重複步驟 2，直到堆的尺寸為 1。
3. 動圖示範（來源 runoob.com）：
3. 具體算法實作
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 typedef struct _Heap
6 {
7 int *arr; //存儲堆元素的數組
8 int size; //目前已存儲的元素個數
9 int capacity; //目前存儲的容量
10 }Heap;
11
12 bool initHeap(Heap &heap, int *orginal, int size);
13 bool popMax(Heap &heap, int &value);
14 void heapSort(Heap &heap);
15 static void buildHeap(Heap &heap);
16 static void adjustDown(Heap &heap, int index);
17
18 /*初始化堆*/
19 bool initHeap(Heap &heap, int *orginal, int size)
20 {
21 //heap.arr = new int[capacity];
22 heap.arr = orginal;
23 if (!heap.arr) return false;
24
25 heap.capacity = size;
26 heap.size = size;
27
28 //如果存在原始資料則建構堆
29 if(size > 0)
30 {
31 //方式一: 直接調整所有元素
32 //建堆
33 buildHeap(heap);
34 }
35 return true;
36 }
37
38 /* 從最後一個父節點(size/2-1 的位置)逐個往前調整所有父節點（直到根節點）, 確定每一個父節點都是一個最大堆，最後整體上形成一個最大堆 */
39 void buildHeap(Heap &heap)
40 {
41 int i;
42 for (i = heap.size / 2 - 1; i >= 0; i--)
43 {
44 adjustDown(heap, i);
45 }
46 }
47
48 /*将目前的節點和子節點調整成最大堆*/
49 void adjustDown(Heap &heap, int index)
50 {
51 int cur = heap.arr[index]; //目前待調整的節點
52 int parent, child;
53
54 /*判斷否存在大于目前節點子節點，如果不存在 ，則堆本身是平衡的，不需要調整；
55 如果存在，則将最大的子節點與之交換，交換後，如果這個子節點還有子節點，則要繼續
56 按照同樣的步驟對這個子節點進行調整*/
57 for (parent = index; (parent * 2 + 1)<heap.size; parent = child)
58 {
59 child = parent * 2 + 1;
60 //取兩個子節點中的最大的節點
61 if (((child + 1)<heap.size) && (heap.arr[child]<heap.arr[child + 1]))
62 {
63 child++;
64 }
65 //判斷最大的節點是否大于目前的父節點
66 if (cur >= heap.arr[child])
67 {
68 //不大于，則不需要調整，跳出循環
69 break;
70 }
71 else
72 {
73 //大于目前的父節點，進行交換，然後從子節點位置繼續向下調整
74 heap.arr[parent] = heap.arr[child];
75 heap.arr[child] = cur;
76 }
77 }
78 }
79
80 /* 實作堆排序 */
81 void heapSort(Heap &heap)
82 {
83 if (heap.size<1) return ;
84 while(heap.size>0)
85 {
86 int tmp = heap.arr[0];
87 heap.arr[0] = heap.arr[heap.size-1];
88 heap.arr[heap.size-1] = tmp;
89 heap.size--;
90 adjustDown(heap, 0);// 向下執行堆調整
91 }
92 }
93
94 /* 删除最大的節點，并獲得節點的值*/
95 bool popMax(Heap &heap, int &value)
96 {
97 if (heap.size<1) return false;
98 value = heap.arr[0];
99 heap.arr[0] = heap.arr[--heap.size];
100 //heap.arr[0] = heap.arr[heap.size-1];
101 //heap.size--;
102 adjustDown(heap, 0);// 向下執行堆調整
103 return true;
104 }
105
106 int main(void)
107 {
108 Heap hp;
109 int origVals[] = { 1, 2, 3, 87, 93, 82, 92, 86, 95 };
110 int i = 0;
111 if(!initHeap(hp, origVals, sizeof(origVals)/sizeof(origVals[0])))
112 {
113 fprintf(stderr, "初始化堆失敗！\n");
114 exit(-1);
115 }
116
117 for (i = 0; i<hp.size; i++)
118 {
119 printf("the %dth element:%d\n", i, hp.arr[i]);
120 }
121
122 //執行堆排序
123 heapSort(hp);
124 printf("堆排序後的結果：\n");
125 for(i=0; i<sizeof(origVals)/sizeof(origVals[0]); i++)
126 {
127 printf(" %d", origVals[i]);
128 }
129
130 system("pause");
131 return 0;
132 } ==================================================================================================================