堆[計算機術語]

釋義

堆（英語：heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：

•堆中某個節點的值總是不大於或不小於其父節點的值；

•堆總是一棵完全二叉樹。

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。

堆是線性數據結構，相當於一維數組，有唯一後繼。

堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}若且唯若滿足下關係時，稱之為堆。

(k <= k,k <= k)或者(k >= k,k >= k), (i = 1,2,3,4...n/2)

若將和此次序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。

支持操作

堆支持以下的基本操作:

•build:建立一個空堆；

•insert:向堆中插入一個新元素；

•update：將新元素提升使其符合堆的性質；

•get：獲取當前堆頂元素的值；

•delete：刪除堆頂元素；

•heapify：使刪除堆頂元素的堆再次成為堆。

某些堆實現還支持其他的一些操作，如斐波那契堆支持檢查一個堆中是否存在某個元素。

算法思想

不必將值一個個地插入堆中，通過交換形成堆。假設根的左、右子樹都已是堆，並且根的元素名為R。這種情況下，有兩種可能：

（1） R的值小於或等於其兩個子女，此時堆已完成；

（2） R的值大於其某一個或全部兩個子女的值，此時R應與兩個子女中值較小的一個交換，結果得到一個堆，除非R仍然大於其新子女的一個或全部的兩個。這種情況下，我們只需簡單地繼續這種將R“拉下來”的過程，直至到達某一個層使它小於它的子女，或者它成了葉結點。

篩選法

首先將要排序的所有關鍵碼放到一棵完全二叉樹的各個結點中（這時的完全二叉樹並不具備堆的特性）。顯然，所有的結點Ki都沒有子女結點，因此以這樣的Ki為根的子樹已經是堆，然後從 的結點Ki開始，逐步把以為根的子樹排成堆，直到以K0為根的子樹排成堆，就完成了建堆過程。

在考慮將以Ki為根的子樹排成堆時，以Ki+1，Ki+2，…，Kn-1為根的子樹已經是堆，所以這時如果有Ki≤K2i+1和Ki≤K2i+2，則不必改變任何結點的位置，以Ki為根的子樹就已經是堆；否則就要適當調整子樹中結點的位置以滿足堆的定義。由於Ki的左、右子樹都已經是堆，根結點是堆中最小的結點，所以調整後Ki的值必定是原來K2i+1和K2i+2中較小的一個。不妨假定K2+1較小，將Ki與K2i+1交換位置，這樣調整後Ki≤K2i，Ki≤K2i+1，並且以K2i+2為根的子樹原來已經是堆，不必再作任何調整，只有以K2i+1為根的子樹由於K2i+1的值已經發生變化（與Ki交換了），所以有可能不滿足堆的定義（當K2i+1的左、右子樹已經是堆）。這時可重複上述過程，考慮將K2i+1以為根的子樹排成堆。如此一層一層遞推下去，最多可以一直進行到樹葉。由於每步都保證將子樹中最小的結點交換到子樹的根部，所以這個過程是不會反饋的。它就像過篩一樣，把最小的關鍵碼一層一層選擇出來。

建堆效率

n個結點的堆，高度d =logn。根為第0層，則第i層結點個數為2i，考慮一個元素在堆中向下移動的距離。大約一半的結點深度為d-1，不移動（葉）。四分之一的結點深度為d-2，而它們至多能向下移動一層。樹中每向上一層，結點的數目為前一層的一半，而子樹高度加一。

這種算法時間代價為Ο（n)

由於堆有log n層深，插入結點、刪除普通元素和刪除最小元素的平均時間代價和時間複雜度都是

Ο（log n）。

操作實現

在程式中，堆用於動態分配和釋放程式所使用的對象。在以下情況中調用堆操作：

1.事先不知道程式所需對象的數量和大小。

2.對象太大，不適合使用堆疊分配器。

堆使用運行期間分配給代碼和堆疊以外的部分記憶體。

傳統上，作業系統和運行時庫隨附了堆實現。當進程開始時，作業系統創建稱為進程堆的默認堆。如果沒有使用其他堆，則使用進程堆分配塊。語言運行時庫也可在一個進程內創建單獨的堆。（例如，C 運行時庫創建自己的堆。）除這些專用堆外，應用程式或許多載入的動態程式庫 (DLL) 之一也可以創建並使用單獨的堆。Win32 提供了一組豐富的 API用於創建和使用專用堆。有關堆函式的優秀教程，請參閱 MSDN 平台 SDK 節點。

當應用程式或 DLL 創建專用堆時，這些堆駐留於進程空間中並且在進程範圍內是可訪問的。某一給定堆分配的任何數據應為同一堆所釋放。（從一個堆分配並釋放給另一個堆沒有意義。）

在所有虛擬記憶體系統中，堆位於作業系統的虛擬記憶體管理器之上。語言運行時堆也駐留在虛擬記憶體之上。某些情況下，這些堆在作業系統堆的上層，但語言運行時堆通過分配大的塊來執行自己的記憶體管理。繞開作業系統堆來使用虛擬記憶體函式可使堆更好地分配和使用塊。

典型的堆實現由前端分配器和後端分配器組成。前端分配器維護固定大小塊的自由列表。當堆收到分配調用後，它嘗試從前端列表中查找自由塊。如果此操作失敗，則堆將被迫從後端（保留和提交虛擬記憶體）分配一個大塊來滿足請求。通常的實現具有每個塊分配的開銷，這花費了執行周期，也減少了可用存儲區。

Windows NT的實現（Windows NT 4.0 版及更高版本）使用 127 個從 8 到 1,024 位元組不等的 8 位元組對齊塊的自由列表和 1 個混合列表。混合列表（自由列表【0】）包含大小超過 1,024 位元組的塊。自由列表包含在雙向連結表中連結在一起的對象。默認情況下，進程堆執行合併操作。（合併操作是組合相鄰的自由塊以生成更大的塊的操作。）合併操作花費了額外的周期，但減少了堆塊的內部碎片。

單個全局鎖可防止多執行緒同時使用堆。此鎖主要用於保護堆數據結構不受多執行緒的任意訪問。當堆操作過於頻繁時，此鎖會對性能造成負面影響。

代碼實現

c++實現

VB.net實現