堆(計算機術語):釋義,支持操作,算法思想,篩選法,建堆效率,操作實現,代碼實現,

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

基本介紹

中文名：堆
外文名：heap
定義：一類特殊的數據結構的統稱
物理特性：一棵完全二叉樹

釋義,支持操作,算法思想,篩選法,建堆效率,操作實現,代碼實現,

釋義

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

堆中某個節點的值總是不大於或不小於其父節點的值；
堆總是一棵完全二叉樹。

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

堆是非線性數據結構，相當於一維數組，有兩個直接後繼。

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

(k_i <= k_2i,k_i <= k_2i+1)或者(k_i >= k_2i,k_i >= k_2i+1), (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 =log₂n。根為第0層，則第i層結點個數為2^i，考慮一個元素在堆中向下移動的距離。大約一半的結點深度為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++實現

#pragma oncetemplate<class T>class JBMinHeap{private:    //申請堆空間    T *_minHeap = NULL;    int _index,_maxSize;public:    JBMinHeap(int maxSize) {        _maxSize = maxSize;        _minHeap = new T[_maxSize];        _index = -1;    }    JBMinHeap(JBMinHeap &h) {        _index = h._index;        _maxSize = h._maxSize;        _minHeap = new T[_maxSize];        for (int i = 0;i<_maxSize) {            *_minHeap[i] = *h._minHeap[i];        }    }    ~JBMinHeap() {        delete[]_minHeap;    }    //獲取整個最小堆的頭部指針    T * getMinHeap() {        return _minHeap;    }    //判斷堆是不是空的    bool isEmpty() {        return _index == -1;    }    bool add(T x) {        if (isFull()) {            return false;        }        _index++;        _minHeap[_index] = x;        return true;    }    bool isFull() {        return _index == _maxSize;    }    //堆進行向下調整    void adjustDown(int index);    //隊進行向上調整    void adjustUp(int index);    //建堆運算    void createMinHeap() {        if (isEmpty()) {            return;        }        for (int i = (_index-1)/2;i >-1;i--) {//直接從倒數第二層 逐層向下調整            adjustDown(i);        }    }};template<class T>void JBMinHeap<T>::adjustDown(int index) {    if (isEmpty()) {        return;    }    while (index<_index)    {        T temp = _minHeap[index];//將當前索引的位置的值保存下來        int oneC = 2 * index + 1;//獲取到兩個孩子的位置        int twoC = 2 * index + 2;        if (oneC == _index) {//若第一個孩子是整個堆最後一個位置 則直接執行交換操作並結束執行                _minHeap[index] = _minHeap[oneC];                _minHeap[oneC] = temp;                return;        }        if (twoC >_index) {//如果第二個孩子的索引位置越界 結束執行            return;        }        if (_minHeap[oneC] <= _minHeap[twoC]) {//正常情況的數據互動執行            if (temp > _minHeap[oneC]) {                _minHeap[index] = _minHeap[oneC];                _minHeap[oneC] = temp;                index = oneC;            }            else {//如果該處索引值已經是比兩個孩子小 則結束循環                index = _index;            }        }        else         {            if (temp > _minHeap[twoC]) {                _minHeap[index] = _minHeap[twoC];                _minHeap[twoC] = temp;                index = twoC;            }            else             {                index = _index;            }        }    }}template<class T>void JBMinHeap<T>::adjustUp(int index) {    if (index > _index) {//大於堆的最大值直接return        return;    }    while (index>-1)    {        T temp = _minHeap[index];        int father = (index - 1) / 2;        if (father >= 0) {//如果索引沒有出界就執行想要的操作            if (temp < _minHeap[father]) {                _minHeap[index] = _minHeap[father];                _minHeap[father] = temp;                index=father;            }            else {//若果已經是比父親大 則直接結束循環                index = -1;            }        }        else//出界就結束循環        {            index = -1;        }    }}

VB.net實現

Public Class Priority_QueueFriend Element() As IntegerFriend point As Integer ReadOnly Property Top As IntegerGetTryReturn Element(1)Catch ex As ExceptionReturn 0End TryEnd GetEnd PropertyReadOnly Property Size As IntegerGetReturn pointEnd GetEnd PropertyReadOnly Property Empty As BooleanGetIf point = 0 Then Return TrueReturn FalseEnd GetEnd Property Sub push(ByVal _ele_val As Integer)point += 1Element(point) = _ele_valDim Now As Integer = pointDim Nxt As Integer = Now / 2While (Now <> 1 AndAlso Element(Now) > Element(Nxt))Swap(Element(Now), Element(Nxt))Now = NxtNxt /= 2End WhileEnd SubSub pop()Dim now As Integer = 1 Element(1) = Element(point)point -= 1 While (1) Dim left As Integer = 0Dim right As Integer = 0 If (now * 2 <= point) Thenleft = Element(now * 2)End IfIf (now * 2 + 1 <= point) Thenright = Element(now * 2 + 1)End If If (right = left And right = 0) ThenExit SubEnd If If (Element(now) < left OrElse Element(now) < right) ThenIf left > right ThenSwap(Element(now), Element(now * 2))now *= 2ElseSwap(Element(now), Element(now * 2 + 1))now *= 2now += 1End IfElseExit WhileEnd IfEnd While End Sub Sub New(ByVal _size As Integer)ReDim Element(_size)point = 0End SubProtected Overrides Sub Finalize()MyBase.Finalize()End Sub End Class

堆(計算機術語)