-
堆
（數據結構）
鎖定
- 中文名
- 堆
- 外文名
- heap
- 定 義
- 一類數據結構的統稱
堆釋義
堆（heap）是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：
- 堆中某個結點的值總是不大於或不小於其父結點的值；
- 堆總是一棵完全二叉樹。
堆的物理結構本質上是順序存儲的，是線性的。但在邏輯上不是線性的，是完全二叉樹的這種邏輯儲存結構。 堆的這個數據結構，裏面的成員包括一維數組，數組的容量，數組元素的個數，有兩個直接後繼。
堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關係時，稱之為堆。
(
且
)或者(
), (
)
若將和此次序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。
堆STL
堆的STL支持以下的基本操作:
make_heap(first, last, comp);
建立一個空堆；
向堆中插入一個新元素；
top_heap(first, last, comp);
獲取當前堆頂元素的值；
sort_heap(first, last, comp);
對當前堆進行排序；
堆算法思想
（1）
並且
，此時堆已完成；
（2）
或者
，此時
應與兩個子女中值較小的一個交換，結果得到一個堆，除非
仍然大於其新子女的一個或全部的兩個。這種情況下，我們只需簡單地繼續這種將
“拉下來”的過程，直至到達某一個層使它小於它的子女，或者它成了葉結點。
堆篩選法
首先將要排序的所有關鍵碼放到一棵完全二叉樹的各個結點中（這時的完全二叉樹並不具備堆的特性）。顯然，所有的結點
都沒有子女結點，因此以這樣的
為根的子樹已經是堆，然後從 的結點Ki開始，逐步把以為根的子樹排成堆，直到以K0為根的子樹排成堆，就完成了建堆過程。
在考慮將以
為根的子樹排成堆時，以
為根的子樹已經是堆，所以這時如果有
和
，則不必改變任何結點的位置，以
為根的子樹就已經是堆；否則就要適當調整子樹中結點的位置以滿足堆的定義。由於Ki的左、右子樹都已經是堆，根結點是堆中最小的結點，所以調整後
的值必定是原來
和
中較小的一個。假設
較小，將
與
交換位置，這樣調整後
，
，並且以
為根的子樹原來已經是堆，不必再作任何調整，只有以
為根的子樹由於
的值已經發生變化（與
交換了），所以有可能不滿足堆的定義（當
的左、右子樹已經是堆）。這時可重複上述過程，考慮將
以為根的子樹排成堆。如此一層一層遞推下去，最多可以一直進行到樹葉。由於每步都保證將子樹中最小的結點交換到子樹的根部，所以這個過程是不會反饋的。它就像過篩一樣，把最小的關鍵碼一層一層選擇出來。
堆建堆效率
堆代碼實現
c++實現
#pragma once
template<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//出界就結束循環1
{
index = -1;
}
}
}
VB.net實現
Public Class Priority_Queue Friend Element() As Integer Friend point As Integer ReadOnly Property Top As Integer Get Try Return Element(1) Catch ex As Exception Return 0 End Try End Get End Property ReadOnly Property Size As Integer Get Return point End Get End Property ReadOnly Property Empty As Boolean Get If point = 0 Then Return True Return False End Get End Property Sub push(ByVal _ele_val As Integer) point += 1 Element(point) = _ele_val Dim Now As Integer = point Dim Nxt As Integer = Now / 2 While (Now <> 1 AndAlso Element(Now) > Element(Nxt)) Swap(Element(Now), Element(Nxt)) Now = Nxt Nxt /= 2 End While End Sub Sub pop() Dim now As Integer = 1 Element(1) = Element(point) point -= 1 While (1) Dim left As Integer = 0 Dim right As Integer = 0 If (now * 2 <= point) Then left = Element(now * 2) End If If (now * 2 + 1 <= point) Then right = Element(now * 2 + 1) End If If (right = left And right = 0) Then Exit Sub End If If (Element(now) < left OrElse Element(now) < right) Then If left > right Then Swap(Element(now), Element(now * 2)) now *= 2 Else Swap(Element(now), Element(now * 2 + 1)) now *= 2 now += 1 End If Else Exit While End If End While End Sub Sub New(ByVal _size As Integer) ReDim Element(_size) point = 0 End Sub Protected Overrides Sub Finalize() MyBase.Finalize() End Sub End Class
