這是數據結構類重新復習筆記的第 五 篇，同專題的其他文章可以移步： /nb/39256701
堆 （Heap）又稱為 優先隊列 （priority queue），在隊列的基礎上，堆允許所有隊列中的元素不壹定按照 先進先出 （FIFO）的規則進行，而是使得每個元素有壹定的優先級，優先級高的先出隊列。
優先隊列至少存在兩個重要的操作：
有幾種簡單而明顯的方法實現優先隊列。
二叉堆 （binary heap）是壹種對於優先隊列的實現，可以簡稱為堆
堆是壹棵 完全二叉樹 （complete binary tree），即所有節點都必須有左右兩個子節點，除了最後壹排元素從左向右填入，直到沒有元素為止。
很顯然，壹棵高為h的完全二叉樹有 2^h 到 2^(h+1)-1 個節點，即其高度為 logN 向下取整。
完全二叉樹的好處在於其規律性，可以使用壹個數組而不需要鏈表來表示
對於數組中任壹位置 i 上的元素，其左兒子在位置 2i 上，右兒子在左兒子後的單元 (2i+1) 上，它的父親則在位置 i/2 向下取整上。
因此，不僅不需要鏈，而且遍歷該樹所需要的操作也極簡單，在大部分計算機上都可能運行得非常快。唯壹問題是最大的堆的大小需要事先估計。
使操作可以快速執行的性質是 堆序性質 （heap-order property）：對於每壹個節點X，X的父節點中的鍵小於等於X中的鍵，除沒有父節點根節點外。
將待插入的元素首先放置在最後壹個位置上，以保證他是壹個完全二叉樹，然後將該元素與其父節點（i/2向下取整）比較，如果比其父節點小，就將兩者互換，互換後再和新的父節點比較，這種方式稱為 上濾 （percolate up），得到壹個小頂堆（min heap），如果比較的時候是較大的值向上走，就會得到壹個大頂堆（max heap）
比如向壹個小頂堆中插入元素14的操作：
找出、返回並刪除最小元非常簡單，最小元就是根節點處的元素，將其返回並刪除。接下來是處理這個B。首先拿下最後壹個元素X，如果元素X比B的兩個子節點都小，可以直接將X插入到B的位置，如果X比B的兩個子節點中的任意壹個大，就不能插入，此時找到兩個子節點中較小的那個放到B處，B轉而移至這個子結點處。重復如上的步驟直到X可以插入B處為止。這個操作成為 下濾 （percolate down）
比如從壹個小頂堆中刪除根節點
decreaseKey(p, A) 操作減小在位置p處的元素的值，減少量為A，可以理解為調高了某個元素的優先級。操作破壞了堆的性質，從而需要上濾操作進行堆的調整。
increaseKey(p, A) 操作增加在位置p處的元素的值，增加量為A，可以理解為降低了某個元素的優先級。操作破壞了堆的性質，從而需要下濾操作進行堆的調整。
remove(p) 操作刪除在堆中位置p處的節點，這種操作可以通過連續執行 decreaseKey(p, ∞) 和 deleteMin() 完成，可以理解馬上刪除某個壹般優先級的元素
即將壹個原始集合構建成二叉堆，這個構造過程即進行N次連續的 insert 操作完成
定理 ：包含 2^(h+1)-1 個節點且高度為h的理想二叉樹（perfect binary tree）的節點的高度和為 2^(h+1)-1-(h+1)
d堆 （d-Heaps）是二叉堆的簡單推廣，它與二叉堆很像，但是每個節點都有d個子節點，所以二叉堆是d為2的d堆。d堆是完全d叉樹。比如下邊的壹個3堆。
d堆比二叉堆淺很多，其insert的運行時間改進到 O(logdN) 。但是deleteMin操作比較費時，因為要在d個子節點中找到最小的壹個，需要進行d-1次比較。d堆無法進行find操作，而且將兩個堆合二為壹是很困難的事情，這個附加操作為merge合並。
註意！ 在尋找節點的父節點、子節點的時候，乘法和除法都有因子d。如果d是壹個2的冪，則可以通過使用二進制的 移位 操作計算，這在計算機中是非常省時間的。但是如果d不是壹個2的冪，則使用壹般的乘除法計算，時間開銷會急劇增加。有證據顯示，實踐中，堆可以勝過二叉堆
這些高級的數據結構很難使用壹個數據結構來實現，所以壹般都要用到鏈式數據結構，這種結構可能會使得其操作變慢。
零路徑長 （null path length）npl(X)：定義為從壹個X節點到其不具有兩個子節點的子節點的最短路徑長，即具有0個或者1個子節點的節點npl=0，npl(null)=-1，任意節點的零路徑長都比其各個子節點中零路徑長最小值多1。
左式堆 （leftist heap）是指對於任意壹個節點X，其左子節點的零路徑長都大於等於其右子節點的零路徑長。很顯然，左式堆趨向於加深左路徑。比如下邊的兩個堆，只有左邊的是左式堆，堆的節點標示的是該節點的零路徑長。
左式堆的實現中，需要有四個值：數據、左指針、右指針和零路徑長。
定理 ：在右路徑上有r個節點的左式堆必然至少有 2^r-1 個節點
merge 是左式堆的基本操作， insert 插入可以看成是壹個單節點的堆與壹個大堆的 merge ， deleteMin 刪除最小值操作可以看成是首先返回、刪除根節點，然後將根節點的左右子樹進行 merge 。所以 merge 是左式堆的基本操作。
假設現在有兩個非空的左式堆H1和H2，merge操作遞歸地進行如下的步驟：
例如如下的兩個堆：
將H2與H1的右子樹（8--17--26）進行merge操作，此時（8--17--26）和H2的merge操作中又需要（8--17--26）和H2的右子堆（7--37--18）進行merge操作……如此遞歸得到如下的堆：
然後根據遞歸的最外層（回到H1和H2的merge的第二步），將上邊合並的堆成為H1的右子堆
此時根節點（3）處出現了左右子堆不符合左式堆的情況，互換左右子堆並更新零路徑長的值
斜堆 （skew heap）是左式堆的自調節形式，實現起來極其簡單。斜堆和左式堆的關系類似於伸展樹和AVL樹之間的關系。斜堆是具有堆序的二叉樹，但是不存在對樹的結構的現限制。不同於左式堆，關於任意結點的零路徑長的任何信息都不保留。斜堆的右路徑在任何時刻都可以任意長，因此，所有操作的最壞情形運行時間均為O(N)。然而，正如伸展樹壹樣，可以證明對任意M次連續操作，總的最壞情形運行時間是 O(MlogN)。因此，斜堆每次操作的 攤還開銷 （amortized cost）為O(logN)
斜堆的基本操作也是merge合並，和左式堆的合並相同，但是不需要對不滿足左右子堆的左式堆條件的節點進行左右子堆的交換。斜堆的交換是無條件的，除右路徑上所有節點的最大者不交換它的左右兒子外，都要進行這種交換。
比如將上述的H1和H2進行merge合並操作
首先進行第壹步，除了交換左右子樹的操作與左式堆不同，其他的操作都相同
將合並的堆作為H1的右子堆並交換左右子堆，得到合並後的斜堆
二項隊列 （binomial queue）支持merge、insert和deleteMin三種操作，並且每次操作的最壞情形運行時間為O(logN)，插入操作平均花費常數時間。
二項隊列不是壹棵堆序的樹，而是堆序的樹的集合，成為 森林 （forest）。堆序樹中的每壹棵都是有約束的 二項樹 （binomial tree）。二項樹是每壹個高度上至多存在壹棵二項樹。高度為0的二項樹是壹棵單節點樹，高度為k的二項樹Bk通過將壹棵二項樹Bk-1附接到另壹棵二項樹Bk-1的根上而構成的。如下圖的二項樹B0、B1、B2、B3和B4。
可以看到二項樹Bk由壹個帶有兒子B0，B1，……，Bk-1的根組成。高度為k的二項樹恰好有2^k個節點，而在深度d處的節點數為二項系數Cdk。
我們可以使用二項樹的集合唯壹地表示任意大小的優先隊列。以大小為13的隊列為例，13的二進制表示為1101，從而我們可以使用二項樹森林B3、B2、B0表示，即二進制表示的數中，第k位為1表示Bk樹出現，第k位為0表示Bk樹不出現。比如上述的堆H1和堆H2可以表示為如下的兩個二項隊列：
二項隊列額merge合並操作非常簡單，以上邊的二項隊列H1、H2為例。需要將其合並成壹個大小為13的隊列，即B3、B2、B0。
首先H2中有壹個B0，H1中沒有，所以H2中的B0可以直接作為新的隊列的B0的樹
其次H1和H2中兩個B1的樹可以合並成壹個新的B2的樹，只需要將其中根節點較小的堆掛到根節點較大的堆的根節點上。這樣就得到了三棵B2堆，將其中根節點最大的堆直接放到新隊列中成為它的B2堆。
最後將兩個B2堆合並成壹個新隊列中的B3堆。
二項隊列的deleteMin很簡單，只需要比較隊列中所有二項堆的根節點，返回和刪除最小的值即可，時間復雜度為O(logN)，然後進行壹次merge操作，也可以使用壹個單獨的空間每次記錄最小值，這樣就可以以O(1)的時間返回。
森林中樹的實現采用“左子右兄弟”的表示方法，然後二項隊列可以使用壹個數組來記錄森林中每個樹的根節點。
例如上邊的合成的二項隊列可以表示成如下的樣子：
STL中，二叉堆是通過 priority_queue 模板類實現的，在頭文件 queue 中，STL實現壹個大頂堆而不是小頂堆，其關鍵的成員函數如下：