問題模式
功能接口
template <typename T> struct PQ{
virtual void insert(T) = 0; //按照優(yōu)先級次序插入詞條
virtual T getMax() = 0; //取出優(yōu)先級最高的詞條
virtual T delMax() = 0; //刪除優(yōu)先級最高的詞條
}; //與其說PQ是數(shù)據(jù)結(jié)構(gòu)获枝，不如說是ADT(Abstract Data Type)勘纯；其不同的實(shí)現(xiàn)方式卧秘，效率及適用場合也各不相同
Stack和Queue，都是PQ的特例——優(yōu)先級完全取決于元素的插入次序
基本實(shí)現(xiàn)——向量
有序向量
BBST
AVL瓢姻、Splay、Red-black：三個接口均只需O(logn)時間
但是音诈，BBST的功能遠(yuǎn)遠(yuǎn)超過了PQ的需求
PQ = 1 * insert() + 0.5 * search() + 0.5 * remove() = 2/3 * BBST
若只需查找極值元幻碱，則不必維護(hù)所有元素之間的全序關(guān)系，偏序足矣
因此存在某種更為簡單改艇、維護(hù)成本更低的實(shí)現(xiàn)方式收班，使得各功能接口時間復(fù)雜度依然為O(logn)，而且實(shí)際效率更高
完全二叉樹Complete Binary Tree
平衡因子處處非負(fù)的AVL
結(jié)構(gòu)性
邏輯上谒兄，等同于完全二叉樹
物理上摔桦，直接借助向量實(shí)現(xiàn)
邏輯節(jié)點(diǎn)與物理元素依層次遍歷次序彼此對應(yīng)
#define Parent(i) ((i-1)>>1)
#define LChild(i) (1+((i)<<1)) //奇數(shù)
#define RChild(i) ((1+(i)) <<1) //偶數(shù)
PQ_ComplHead = PQ + Vector
template <typename T> class PQ_ComplHeap : public PQ<T>, public Vector<T>{
protected: Rank percolateDown(Rank n, Rank i); //下濾
? ? ? ? ? ? ? ? ?Rank percolateUp(Rank i); //上濾
? ? ? ? ? ? ? ? ?void heapify(Rank n); //Floyd建堆算法
public: PQ_ComplHead(T* A, Rank n); //批次構(gòu)造
? ? ? ? ? ? ? ? { copyFrom(A,0,n); heapify(n);}
? ? ? ? ? ? void insert(T); //按照比較器確定的優(yōu)先級次序，插入詞條
? ? ? ? ? ? T getMax() { return _elem[0];} //讀取優(yōu)先級最高的詞條
? ? ? ? ? ? T delMax(); //刪除優(yōu)先級最高的詞條
};
堆序性
數(shù)值上，只要0<i邻耕，必滿足H[i] <= H[Parent(i)]
故H[0]即是全局最大元素
template <typename T> T PQ_ComplHeap<T>::getMax(){ return _elem[0];}
插入與上濾
為插入詞條e鸥咖，只需將e作為末元素接入向量 //結(jié)構(gòu)性自然保持，若堆序性也亦未破壞兄世，則完成
否則啼辣，e與其父節(jié)點(diǎn)換位 //只能是e與其父節(jié)點(diǎn)違反堆序性，若堆序性因此恢復(fù)御滩，則完成
否則鸥拧，e再與父節(jié)點(diǎn)換位 //依然只可能是e與其（新的）父節(jié)點(diǎn)...
不斷重復(fù)，直到e與其父親滿足堆序性削解，或者e到達(dá)堆頂
實(shí)現(xiàn)
template <typename T> void PQ_ComplHeap<T>::insert(T e)
{ Vector<T>::insert(e); percolateUp(_size - 1);}
template <typename T> Rank PQ_ComplHeap<T>::percolateUp(Rank i){
while(ParentValid(i)){
? ? Rank j = Parent(i);
? ? if( lt( _elem[i], _elem[j] )) break; //一旦父子不再逆序富弦，上濾旋即完成
? ? swap( _elem[i], _elem[j] ); i = j;
}
return i;
}
刪除與下濾
最大元素始終在堆頂，故為刪除之氛驮，只需
摘除向量首元素腕柜，代之以末元素e //結(jié)構(gòu)性保持；若堆序性依然保持則完成
否則e與孩子中的大者換位?
否則e再次與孩子中的大者換位
實(shí)現(xiàn)
template <typename T> T PQ_ComplHeap<T>::delMax(){
? ? T maxElem = _elem[0]; _elem[0] = _elem[--_size];
? ? percolateDown(_size,0);
? ? return maxElem;
}
template <typename T> Rank PQ_ComplHeap<T>::percolateDown(Rank n, Rank i){
? ? Rank j; //i及其（至多兩個）孩子中矫废，堪為父者
? ? while( i != ( j = ProperParent(_elem, n, i))) //只要i非j盏缤，則
? ? ? ? { swap(_elem[i], _elem[j]); i = j; } //換位，并繼續(xù)考察i
? ? return i; //返回下濾抵達(dá)的位置
}
