9-7堆積樹排序法-1
堆積樹排序法可以算是選擇排序法的改進法，它可以減少在選擇排序法中的比較次數，進而減少排序時間。堆積排序法使用到了二元樹的技巧，它是利用堆積樹來完成排序。堆積是一種特殊的二元樹，可分為最大堆積樹及最小堆積樹兩種。而最大堆積樹滿足以下3個條件：
1.它是一個完整二元樹。
2.所有節點的值都大於或等於它左右子節點的值。
3.樹根是堆積樹中最大的。
而為小堆積樹則具備以下3個條件
1.它是一個完整二元樹。
2.所有節點的值都小於會等於它左右子節點的值。
3.樹根是堆積樹中最小的。
在開始討論堆積樹排序法前，各位必須先認識如何將二元樹轉換成堆積樹(heap tree)。我們以下面實例進行說明：
假設有9筆資料32、17、16、24、35、87、65、4、12，我們以二元樹表示如下：
如果要將該二元樹轉換成堆積樹。我們可以用陣列來儲存二元樹所有節點的值，即
1.A[0]=32為樹根，若A[1]大於父節點則必須互換。此處A[1]=17<A[0]=32故不交換。
2.A[2]=16<A[0]故不交換。
3.A[3]=24>A[1]=17 故交換
4.A[4]=35>A[1]=24 故交換，再與A[0]=32比較，A[1]=35>A[0]=32 故交換
5.A[5]=87>A[2]=16 故交換，再與A[0]35比較，A[2]=87>A[0]=35 故交換
6.A[6]=65>A[2]=35 故交換，且A[2]=65<A[0]=87 故不必換。
7.A[7]=4<A[3]=17 故不必換。
A[8]=12<A[3]=17 故不必換。
可得下列的堆積樹
剛才示範由二元樹的樹根開始由上往下逐一依堆積樹的建立原則來改變個節點值，最終得到一最大堆積樹。各位可以發現堆積樹並非唯一，您也可以由陣列最後一個元素(例如此例中的A[8])由下往上逐一比較來建立最大堆積樹。如果您想由小到大排序，就必須建立最小堆積樹，做法和建立最大堆積樹類似，在此不另外說明。