3. 堆排序
已經介紹過了兩種相對簡單的排序算法（插入排序、合并排序）之後，我們将介紹一種稍微難一些的排序算法——堆排序（heapsort）。
堆排序在運作時間上與合并排序相似，同時又是一種原地(in place)排序算法（在任何時候，數組中隻有常數個元素存儲在輸入數組以外），結合了插入排序和合并排序兩種排序算法的優點。
3.1 堆
（二叉）堆資料結構是一種數組對象，它可以被視為一棵完全二叉樹。數中每個節點與數組中存放該節點值的那個元素對應（如圖3-1,3-2所示）。
一個最大堆可以看作一棵二叉樹（如圖3-1所示），也可以看作一個數組（如圖3-2所示）。
二叉樹中：
圓圈中的數字表示數中每個節點存儲的值，節點上方的數字表示對應的數組下标。
數組中：
數組上下的連線表示父子關系，且父節點總是在子節點的左邊。
這裡需要簡單的補充一些知識：
最大堆，堆中的最大元素存放在根節點中，并且，在以某一個節點為根的字數中，各節點的值都不大于該子樹根節點的值。圖3-1所示的二叉樹就可以稱之為最大堆。
3.2 建堆
建堆是指将“原數組所等價的堆”轉換為“最大堆”的過程。
從最後一個子樹（即從以标号為i/2的節點為父節點的子樹）開始，自底向上地建立最大堆。以原數組為{4,1,3,2,16,9,10,14,8,7}為例，其具體過程如圖3-3所示。
過程詳細解釋如下（若了解過程，可跳過此段）：
A）：一個包含10個元素的數組，将其表示為堆的形式。從父節點标号為5（10/2=5）的子樹開始，自底向上建構最大堆。由于16>7，故此時該子樹符合最大堆性質，故不做修改。然後，将目标父節點标号減一變為4，即對父節點标号為4的子樹建構最大堆。
B）：對于父節點标号為4的子樹，由于14>8>2，故将節點标号為4（其值為2）與節點标号為8（其值為14）的值互換。值互換之後，父節點标号為4的子樹符合最大堆性質，故此子樹的最大堆建構完成。然後，将目标父節點标号減一變為3，即對父節點标号為3的子樹建構最大堆。
C）：對于父節點标号為3的子樹，由于10>9>3，故将節點标号為3（其值為3）與節點标号為7（其值為10）的值互換。值互換之後，父節點标号為3的子樹符合最大堆性質，故此子樹的最大堆建構完成。然後，将目标父節點标号減一變為2，即對父節點标号為3的子樹建構最大堆。
D）：對于父節點标号為2的子樹，由于16>14>1，故将節點标号為2（其值為1）與節點标号為5（其值為16）的值互換。與之前不同的是，此時值互換之後，父節點标号為2的子樹并不滿足最大堆性質，故将目标父節點變換至标号為5的節點。由于7>1，故将節點标号為5（其值為1）與節點标号為10（其值為7）的值互換。值互換之後，父節點标号為2的子樹滿足最大堆性質。故繼續如C中所示，将目标父節點變為1，即對父節點标号為1的子樹（即整個二叉樹）建構最大堆。
E）：對于父節點标号為1的子樹，由10>4>1，故将節點标号為1（其值為4）與節點标号為2（其值為16）的值互換。與D中相同，值互換之後，父節點标号為1的子樹并不滿足最大堆性質，故将目标父節點變化至标号為2的節點。由于14>7>4，故将節點标号為2（其值為4）與節點标号為4（其值為14）的值互換。值互換之後，父節點标号為1的子樹仍然不滿足最大堆特征，故将目标父節點變換至标号為4的節點。由于8>4>2，故将節點标号為4（其值為4）與節點标号為9（其值為8）的值互換。值互換之後，父節點标号為1的子樹（即整個二叉樹）滿足最大堆性質。
至此，建立最大堆的過程完成。
3.3 堆排序
對于數組A[1]……A[n]，通過建構最大堆可知，數組中最大的元素在A[1]，則可以通過把A[1]與A[n]互換，使該數字達到最終正确的位置。現在，如果從堆中“去掉”節點n，則可以較容易地建構數組A[1]……A[n-1]的最大堆（即隻需要重新建構目标父節點标号為1的子樹）。此後不斷重複這一過程，直至堆的大小降為1，此時，即完成了最終的排序過程。其具體過程如圖3-6所示。
以a)到b)的轉換過程為例，對該過程進行細部詳解，如圖3-7所示。
C代碼實作如下：
C++代碼實作：