我相信大家都用過STL中的priority_queue馒胆，并且你可能也知道其底層原理是二叉堆（binary heap），但是你真正了解它具體是怎么實現(xiàn)的嗎仗嗦？你能自己寫個優(yōu)先隊列模板而不用STL中的嗎晕拆？刨根問底才是學(xué)習(xí)的最高境界（當(dāng)然，這里探討的只是簡單的實現(xiàn)）橘忱。
優(yōu)先隊列模型
二叉堆
對于優(yōu)先隊列的實現(xiàn)，二叉堆的使用很常見谚咬。與二叉查找樹（binary search tree）一樣鹦付，堆也有兩個性質(zhì)，即結(jié)構(gòu)性質(zhì)和堆序性質(zhì)择卦。類似于AVL樹，對堆的操作可能破壞其中一個性質(zhì)郎嫁，因此秉继，堆的操作必須到堆的所有性質(zhì)都被滿足是才能終止。
結(jié)構(gòu)性質(zhì)
堆是一棵完全二叉樹（complete binary tree）泽铛。我們知道尚辑，一棵高為 h 的完全二叉樹有 2h 到 2h+1-1 個結(jié)點。這意味著盔腔，完全二叉樹的高為O(logN)杠茬。
一個重要的觀察發(fā)現(xiàn)，因為完全二叉樹很有規(guī)律弛随，所以可以用一個數(shù)組表示而不需要使用鏈瓢喉。下圖2中的數(shù)組對應(yīng)著圖1中用二叉樹表示的堆。
對于數(shù)組中任一位置 i 上的元素,其左兒崽在位置 2i 上舀透，右兒子在位置 2i+1 中栓票，它的父親則在位置 i /2
上。因此愕够，這里不僅不需要鏈走贪，而且遍歷該樹所需要的操作也極為簡單。這種實現(xiàn)方法的唯一問題在于惑芭，最大的堆大小需要事先估計坠狡，但一般情況下這并不成問題（而且如果需要我們可以重新調(diào)整）。
因此遂跟，一個堆數(shù)據(jù)結(jié)構(gòu)由一個數(shù)組（Comparable對象的）和一個代表當(dāng)前堆大小的整數(shù)組成逃沿。下面的代碼為一個優(yōu)先隊列接口：
template<typename Comparable>
class BinaryHeap
{
public:
// constructor
explicit BinaryHeap(int capacity = 100);
explicit BinaryHeap(const vector<Comparable>& items);
bool isEmpty() const;
const Comparable& findMin() const;
void insert(const Comparable& x);
void deleteMin();
void deleteMin(const Comparable& minItem);
void makeEmpty();
void printArray();
private:
int currentSize; //Number of elements in heap
vector<Comparable> array; //The heap array
void buildHeap();
void percolateDown(int hole);
};
我們始終把堆畫成樹婴渡，是便于理解，但實際上具體的實現(xiàn)是采用簡單的數(shù)組感挥。
堆序性質(zhì)
使操作可以快速執(zhí)行的性質(zhì)是堆序性質(zhì)（heap-order property）缩搅。由于想要快速地找出最小元，因此最小元應(yīng)該在根上触幼。如果考慮任意子樹也應(yīng)該是堆硼瓣，那么任意結(jié)點就應(yīng)該小于它的所有后裔。
應(yīng)用這個邏輯置谦，可以得到堆序性質(zhì)堂鲤。在堆中，對于每一個結(jié)點 X媒峡，X 的父親中的鍵小于或等于 X 中的鍵瘟栖，根節(jié)點除外（它沒有父親）。下圖左邊的樹是一個堆谅阿，但是半哟，右邊的不是。
根據(jù)堆序性質(zhì)签餐，最小元總可以在根處找到寓涨。因此，我們可以以 O(1) 時間得到附加操作 findMin氯檐。
基本的堆操作
1. insert
為將一個元素 X 插入到堆中戒良，我們在下一個空閑位置創(chuàng)建一個空穴。如果 X 可以放在空穴中而不破壞堆序性質(zhì)冠摄，那么插入完成糯崎。否則，按上濾（percolate up）策略進行河泳，該操作如下圖所示：
使用下面的代碼很容易實現(xiàn)插入：
/**
* Insert item x, allowing duplicates.
*/
template<class Comparable>
void BinaryHeap<Comparable>::insert(const Comparable& x)
{
if (currentSize == array.size() - 1)
{
array.resize(array.size() * 2);
}
// percolate up(上濾)
int hole = ++currentSize;
for (; hole > 1 && x < array[hole/2]; hole /= 2) //array[0] don't put heap element
{
array[hole] = array[hole / 2];
}
array[hole] = x;
}
我們本可以通過反復(fù)實施交換操作直至建立正確的順序來實現(xiàn)上濾過程，可是一次交換需要 3 條賦值語句乔询。如果一個元素上濾 d 層樟插，那么由于交換而實施的賦值次數(shù)達(dá)到 3d，而這里的代碼只需要 d+1 次賦值竿刁。
顯然黄锤，insert 操作的最壞時間復(fù)雜度為 O(logN)。平均看來食拜，這種上濾終止得要早鸵熟；業(yè)已證明，其平均時間復(fù)雜度為 O(1)负甸。
2. deleteMin
findMin操作是簡單的流强，困難的部分在于：刪除它痹届。我們的策略是用堆中最后一個元素替換根，然后實行下濾（percolate down）操作打月。如下圖所示：
在堆的實現(xiàn)中經(jīng)常發(fā)生的錯誤為：當(dāng)堆中存在偶數(shù)個元素時队腐，最后一個非葉子結(jié)點將只有一個崽崽，我們每次都是取崽崽中小的那個作為下濾的對象奏篙，所以這個時候就需要一個附加的測試柴淘。下面代碼的 if 語句中的 child != currentSize 避免了這個容易發(fā)生的錯誤。
/**
* Remove the minimum item.
* Throws UnderflowException if empty.
*/
template<typename Comparable>
void BinaryHeap<Comparable>::deleteMin()
{
if (isEmpty())
{
//throw UnderflowException();
cout << "the array is empty!";
}
array[1] = array[currentSize--];
percolateDown(1);
}
/**
* Internal method to percolate down in the heap.
* hole is the index which the percolate down begins.
*/
template<typename Comparable>
void BinaryHeap<Comparable>::percolateDown(int hole)
{
Comparable temp = array[hole];
int child;
for (; hole * 2 <= currentSize; hole = child)
{
child = hole * 2;
if (child != currentSize && array[child + 1] < array[child])
{
child++;
}
if (array[child] < temp)
{
array[hole] = array[child];
}
else
{
break;
}
}
array[hole] = temp;
}
這種操作的平均運行時間為 O(logN)秘通。
3. buildHeap
初始堆通過項的原始集合來構(gòu)造为严。構(gòu)造函數(shù)將 N 項作為輸入并把它們放入一個堆中。顯然肺稀，這可以通過 N 次連續(xù)的 insert 來完成第股。由于每個 insert 操作都花費 O(1) 的平均時間，以及 O(logN) 的最壞情形時間话原，這個算法的總的運行時間就是 O(logN) 平均時間夕吻，其最壞情形時間為 O(NlogN)。
通常的算法是將 N 項以任意順序放入樹中繁仁，并保持結(jié)構(gòu)特性梭冠。然后從最后一個非葉子結(jié)點開始，一直到根改备，對這些結(jié)點執(zhí)行下濾（percolate down）操作，可以保證能夠生成一棵具有堆序性質(zhì)的樹（heap-ordered tree）蔓倍。
template<class Comparable>
BinaryHeap<Comparable>::BinaryHeap(const vector<Comparable>& items):currentSize(items.size()),array(items.size()+10)
{
/*currentSize = items.size();
array(items.size() + 10);*/
for (int i = 0; i < (int)items.size(); ++i)
{
array[i + 1] = items[i];
}
this->buildHeap();
}
/**
* Establish heap order property from an arbitrary arrangement of items.
* Runs in linear time.
*/
template<typename Comparable>
void BinaryHeap<Comparable>::buildHeap()
{
for (int i = currentSize / 2; i > 0; --i)
{
percolateDown(i);
}
}
可以證明（略）：buildHeap 的運行時間的界為：O(N)悬钳。
以上，便是優(yōu)先隊列的具體實現(xiàn)偶翅。我在文章開頭說了默勾，這只是基本的實現(xiàn)，高級實現(xiàn)還遠(yuǎn)遠(yuǎn)不夠聚谁，包括左式堆母剥、斜堆、二項隊列等等（這些我也還沒看呢嘻嘻）形导。
PS：
看別人的代碼永遠(yuǎn)只是看看环疼，自己將其實現(xiàn)，以后還可以拿來用的勒朵耕，到時候需要另外的功能自己擴充就行了 sha 炫隶！
有什么error評論指出來啊Ｑ植堋Ｎ苯住煞檩！
