2.6.2　最大最小堆

除了快速排序，堆排序也相對比較常用。這里特別介紹最大最小堆，它其實就是堆排序的優先級隊列。堆排序本身是由完全二叉樹這樣的結構支撐的，普通堆排序比快速排序更低效，但堆排序中的最大最小堆的優先級隊列非常有用，即只關注最大值或最小值，在不斷增加和刪除根節點元素的情況下仍可獲取最大值或最小值。優先級隊列完成排序后，數據堆就成了一個頭頂著一個最大值或最小值的數據結構，這種數據結構更有利于獲取根節點的最大最小值節點，在后面的程序邏輯中，當需要插入新元素、修改舊元素及推出最大最小值時，效率比較高。優先級隊列在實時獲取最大最小值時高效的特點，導致它在尋路系統的A星算法中特別有用，因此最大最小堆排序常用于A星算法。

由于堆排序是一種完全二叉樹結構，所以這種結構可以用一維數組表示，這樣會讓效率更高，因為內存是連續的。使用一維數組表示二叉樹時，通常是以完全二叉樹形式表示每個節點及其子節點，每個節點一一對應數組上的索引規則，即如果i為節點索引，i2和i2+1就是它的兩個子節點，而索引i的父節點位置可以用i/2來表示，數組中的任何節點都應遵循這種規則。以此類推到子節點，即(i2)2和(i2)2+1就是i2這個索引的兩個子節點，所有子節點自身的索引直接除以2就是父節點的索引，即i2和i×2+1各除以2后取整就是它們的父節點索引i。

最大最小堆的優先級隊列的操作分為插入元素、返回最大或最小值、返回并刪除最大最小值、查找并修改某個元素，其中關鍵的算法在于插入新元素和刪除最大最小元素。其基本思想是，利用完全二叉樹的特性，將新元素放入二叉樹的葉子節點上，然后比較它與父節點的大小，如果它比父節點大（最小堆的情況），則結束，否則就與父節點交換，繼續比較，直到沒有父節點或者父節點比它小為止。刪除根節點則反過來，把最后一個葉子節點放入根節點，然后找到這個新根節點的實際位置，即比較它與兩個子節點的大小，如果比它們小（最小堆的情況），則結束，否則取最小值（最小堆的情況）替換節點位置，然后再繼續向下比較和替換，直到停止或者替換到葉子節點時再沒有子節點可比較為止，這樣就算完成了操作。

圖2-3和圖2-4能很好地理解插入與刪除的步驟。

圖2-3　插入時的堆排序步驟

圖2-4　刪除根節點步驟

圖2-3為插入時的堆排序步驟，在此過程中，不斷與父節點比較并交換，直到到達根節點或者無法交換為止。圖2-4為刪除根節點的情況，此過程中把根節點與葉子節點交換后，葉子節點再從根部不斷比較并下移到應有的位置。