優先級隊列
優先級隊列是一個由相同類型的數據元素組成的集合，其中每個數據項都帶有一個特定的優先級。它支持insert元素操作，findMin訪問優先級最小元素的操作，deleteMin刪除優先級最小元素的操作，當然，也可能是支持findMax訪問優先級最大元素的操作，deleteMax刪除優先級最大元素的操作，以需求而定。
有兩種很自然的方法來實現優先級隊列：
一種是使用無序隊列（數組、向量或鏈表實現）。兩種基本操作的實現方法及時間復雜度如下：
插入：把數據項插入到隊尾或隊頭。時間復雜度：O(1)。
刪除：遍歷隊列找出優先級最高或最低的項，然後刪除。時間復雜度：O(n)。
另一種是使用有序隊列（數組、向量或鏈表實現）。
兩種基本操作的實現方法及時間復雜度如下：
插入：基本線性插入排序。時間復雜度：O(n)。
刪除：刪除隊頭和隊尾的項。時間復雜度：O(1)。
當然，還有一個可能的實現是二叉查找樹，但二叉查找樹很容易變得不平衡，這樣，插入和刪除效率便會大大降低，另外，二叉查找樹實現了比優先級隊列更多的功能，可以想見，它必然也消耗了更多的資源。所以，將二叉查找樹用作優先級隊列的實現，實在太大材小用了。
當當當當！我們今天的主角登場了。堆，或稱作二叉堆，是“已知的最優雅的數據結構之一”。堆是實現優先級隊列的典型方法，兩種基本操作時間復雜度如下：
插入：最壞情況下時間復雜度為O(logn)；平均情況下時間復雜度為O(1)，業已證明，執行一次插入平均需要 2.607 次比較，因此平均 insert 操作上移元素 1.607層。
刪除：在平均情況和最壞情況下時間復雜度均為O(logn)。
表現簡直完美！STL中的priority_queue類模板就是采用二叉堆來實現的。
堆
堆是符合下列性質的二叉樹：
結構屬性：堆是一棵完全樹。
順序屬性：每個結點中的數據項都大於或等於兒子的數據項。
以上的順序結構是針對最大堆而言的，最小堆的敘述則恰好相反。下面的講解都默認為最大堆。
一般采用數組或向量來實現堆，初次接觸這個事實可能會感到奇怪，因為我們所接觸過的樹結構都是使用鏈式結構來實現的。采用數組或向量來實現堆效率更高，這主要是因為堆沒有在中間位置刪除和插入元素的需求，另外堆是一棵完全樹，方便索引。
一個最大堆結構如下圖所示，它既是一棵二叉樹，也是一個數組。
我們來看看堆的基本操作:
1、 插入操作（insert）
插入操作的過程很簡單：將新數據插入到堆的下一個空位，然後向上滲透直到二叉樹重新滿足堆的順序屬性為止。
實現代碼：
[cpp]
插入操作在平均情況下花費常量時間，在最壞情況下花費對數時間
//業已證明，執行一次插入平均需要 2.607 次比較，因此平均 insert 操作
//上移元素 1.607層。
template<typename T>
void BinaryHeap<T>::insert(const T& value)
{
if(theSize+1==theArray.size())
theArray.resize(theArray.size()*2);
int hole = ++theSize;
//hole==1時已是最高點，不可向上滲透了。
for(;value<theArray[hole/2]&&hole>1;hole/=2)
theArray[hole] = theArray[hole/2];
theArray[hole] = value;
}
//插入操作在平均情況下花費常量時間，在最壞情況下花費對數時間
//業已證明，執行一次插入平均需要 2.607 次比較，因此平均 insert 操作
//上移元素 1.607層。
template<typename T>
void BinaryHeap<T>::insert(const T& value)
{
if(theSize+1==theArray.size())
theArray.resize(theArray.size()*2);
int hole = ++theSize;
//hole==1時已是最高點，不可向上滲透了。
for(;value<theArray[hole/2]&&hole>1;hole/=2)
theArray[hole] = theArray[hole/2];
theArray[hole] = value;
}
2、下濾操作（percolate down）
近似堆的定義是，二叉樹根結點的左右子樹均為堆，但整體不滿足堆的順序屬性。下濾操作是把近似堆調整為堆的過程。
該過程也很簡單：找到一個較大的兒子，如果該結點比兒子小，則和兒子交換位置。重復上述過程直到二叉樹滿足堆的順序屬性。
下圖展示了對結點2進行下濾操作的過程。
實現代碼：
[cpp]
template<typename T>
void BinaryHeap<T>::percolateDown(int hole)
{
int child;
T temp = theArray[hole];
for (;hole*2<=theSize;hole=child)
{
child = hole*2;
if(child!=theSize && theArray[child+1]<theArray[child])
++child;
if(theArray[child]<temp)
theArray[hole]=theArray[child];
else
break;
}
theArray[hole]=temp;
}
template<typename T>
void BinaryHeap<T>::percolateDown(int hole)
{
int child;
T temp = theArray[hole];
for (;hole*2<=theSize;hole=child)
{
child = hole*2;
if(child!=theSize && theArray[child+1]<theArray[child])
++child;
if(theArray[child]<temp)
theArray[hole]=theArray[child];
else
break;
}
theArray[hole]=temp;
}我並沒有單獨列出刪除操作（delete），這是因為刪除操作主要過程就是下濾操作：刪除根結點，將堆最後面的數據項復制到根結點，執行下濾操作。
實現代碼：
[cpp]
刪除操作在平均情況和最壞情況下都需要對數時間
template<typename T>
void BinaryHeap<T>::deleteMin()
{
if(isEmpty())
throw exception();
theArray[1]=theArray[theSize--];
percolateDown(1);
}
//刪除操作在平均情況和最壞情況下都需要對數時間
template<typename T>
void BinaryHeap<T>::deleteMin()
{
if(isEmpty())
throw exception();
theArray[1]=theArray[theSize--];
percolateDown(1);
}
3、 建堆操作（build heap）
建堆操作是把一棵完全二叉樹轉換成堆。這是堆排序中的關鍵操作。該操作的具體過程為：從最後一個非葉子節點開始到根結點，依次執行下濾操作。
下圖展示了構建一個最大堆的過程。
實現代碼：
[cpp]
template<typename T>
void BinaryHeap<T>::buildHeap()
{
for(int i=theSize/2;i>0;--i)
percolateDown(i);
}
template<typename T>
void BinaryHeap<T>::buildHeap()
{
for(int i=theSize/2;i>0;--i)
percolateDown(i);
}
點擊此處查看最小堆類模板完整源代碼
堆排序
顧名思義，堆排序是利用堆的特性來對一組數據進行排序。堆排序可分為以下個步驟（從小到大排序）：
對所有n個數據進行建堆（最大堆）操作。
將堆頂元素和堆尾元素交換，對剩下的n-1個數據進行建堆（最大堆）操作。
重復步驟2直至堆的大小為1，此時數據完成排序。
有兩個問題需要重視：
被排序的數據從0開始索引，所以父親和孩子的位置都有了相應的變化。父親的位置由i/2變為(i-1)/2，左孩子的位置由2i變為2i+1，右孩子的位置由2i+1變為2i+2。
下濾操作需要知道當前堆的大小。
實現代碼：
[cpp]
template<typename T>
void percolateDown(vector& vec,int i,int length)
{
int child;
T temp = vec[i];
for(;2*i+1<=length-1;i=child)
{
child = 2*i+1;
if(childtemp)
vec[i] = vec[child];
else
break;
}
vec[i] = temp;
}
template<typename T>
void heapSort(vector& vec)
{
for(int i = vec.size()/2;i>=0;--i)
percolateDown(vec,i,vec.size());
for (int j = vec.size()-1;j!=0;--j)
{
swap(vec[0],vec[j]);
percolateDown(vec,0,j);
}
}
void main()
{
int a[]={312,33,44,5,6,4,2,3,4,5,6,76,8,6,88768,5345,43,432};
vector<int> vec(a,a+sizeof(a)/sizeof(*a));
for (int i=0;i!=vec.size();++i)
cout<<vec[i]<<" ";
cout<<endl;
heapSort(vec);
for (int i=0;i!=vec.size();++i)
cout<<vec[i]<<" ";
cout<<endl;
}
template<typename T>
void percolateDown(vector& vec,int i,int length)
{
int child;
T temp = vec[i];
for(;2*i+1<=length-1;i=child)
{
child = 2*i+1;
if(childtemp)
vec[i] = vec[child];
else
break;
}
vec[i] = temp;
}
template<typename T>
void heapSort(vector& vec)
{
for(int i = vec.size()/2;i>=0;--i)
percolateDown(vec,i,vec.size());
for (int j = vec.size()-1;j!=0;--j)
{
swap(vec[0],vec[j]);
percolateDown(vec,0,j);
}
}
void main()
{
int a[]={312,33,44,5,6,4,2,3,4,5,6,76,8,6,88768,5345,43,432};
vector<int> vec(a,a+sizeof(a)/sizeof(*a));
for (int i=0;i!=vec.size();++i)
cout<<vec[i]<<" ";
cout<<endl;
heapSort(vec);
for (int i=0;i!=vec.size();++i)
cout<<vec[i]<<" ";
cout<<endl;
}
在PercolateDown算法中，在每一個階段中考慮的項的數目是前一階段的一半。因此，與二叉查找樹的情況類似，這個算法的最壞計算時間是O(logn)。由於BuildHeap操作執行了n/2次PercolateDown操作，其最壞計算時間是O(nlogn)。HeapSort執行一次BuildHeap操作和n-1次PercolateDown操作，因此其最壞計算時間是O(nlogn)。
