堆檢視原始碼討論檢視歷史
| 堆 |
 |
堆(Heap)是計算機科學中一類特殊的數據結構，是最高效的優先級隊列。堆通常是一個可以被看做一棵完全二叉樹的數組對象。
基本信息
中文名；堆
外文名；heap
定 義；一類數據結構的統稱
釋義
堆（heap）是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質： 堆中某個結點的值總是不大於或不小於其父結點的值； 堆總是一棵完全二叉樹。
將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。 堆是非線性數據結構，相當於一維數組，有兩個直接後繼。
堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關係時，稱之為堆。 (且)或者(), ()
若將和此次序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。
STL
堆的STL包含於 頭文件中。 堆的STL支持以下的基本操作: 1make_heap(first, last, comp); 建立一個空堆； 向堆中插入一個新元素； 1top_heap(first, last, comp); 獲取當前堆頂元素的值； 1sort_heap(first, last, comp); 對當前堆進行排序；
算法思想
不必將值一個個地插入堆中，通過交換形成堆。假設一個小根堆的左、右子樹都已是堆，並且根的元素名為 ，其左右子結點為 和 ，這種情況下，有兩種可能：
（1） 並且 ，此時堆已完成；
（2） 或者 ，此時 應與兩個子女中值較小的一個交換，結果得到一個堆，除非 仍然大於其新子女的一個或全部的兩個。這種情況下，我們只需簡單地繼續這種將 「拉下來」的過程，直至到達某一個層使它小於它的子女，或者它成了葉結點。
篩選法
首先將要排序的所有關鍵碼放到一棵完全二叉樹的各個結點中（這時的完全二叉樹並不具備堆的特性）。顯然，所有的結點 都沒有子女結點，因此以這樣的 為根的子樹已經是堆，然後從 的結點Ki開始，逐步把以為根的子樹排成堆，直到以K0為根的子樹排成堆，就完成了建堆過程。 在考慮將以 為根的子樹排成堆時，以 為根的子樹已經是堆，所以這時如果有 和 ，則不必改變任何結點的位置，以 為根的子樹就已經是堆；否則就要適當調整子樹中結點的位置以滿足堆的定義。由於Ki的左、右子樹都已經是堆，根結點是堆中最小的結點，所以調整後 的值必定是原來 和 中較小的一個。假設 較小，將 與 交換位置，這樣調整後，，並且以 為根的子樹原來已經是堆，不必再作任何調整，只有以為根的子樹由於的值已經發生變化（與交換了），所以有可能不滿足堆的定義（當的左、右子樹已經是堆）。這時可重複上述過程，考慮將以為根的子樹排成堆。如此一層一層遞推下去，最多可以一直進行到樹葉。由於每步都保證將子樹中最小的結點交換到子樹的根部，所以這個過程是不會反饋的。它就像過篩一樣，把最小的關鍵碼一層一層選擇出來。[1]