如果定義最小值為最高優先權, 使用最小堆為例.? 每次入隊新元素都要向上調整, 同理, 彈出優先權最高的元素時要向下調整,?使之成為堆. 將新元素插入p[j]后的調整工作由AdjustUp()函數完成, 該函數按照與函數AdjustDown()相反的方向比較路徑, 由下向上, 與雙親結點進行比較. 若雙親結點的元素值比孩子結點元素值大, 則調整之, 直到或者其雙親不大于待插入元素, 或者以及到達堆頂. 程序中首先將新元素插在q[j]處, 令tmp元素等于新元素q[j], 從i = j開始, 將tmp與其雙親q[(i - 1) / 2]比較. 如果tmp小于q[(i - 1) / 2], 則將q[(i - 1) / 2]向下移到q[i]處, 直到或者tmp >= q[(i - 1) / 2], 或者已達到堆頂. 若優先隊列未滿, 則函數Append()首先在優先隊列的最后插入新元素, 然后調用AdjustUp()進行向上調整, 將隊列重新調整為堆. 若優先隊列非空, 則函數Sever()首先將堆頂元素賦值給x, 然后將原來的堆底元素取代堆頂元素, 同時讓堆大小減一, 最后使用調用函數AdjustDown()進行向下調整. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "cassert" using namespace std; template <class T> class PrioQueue { public: PrioQueue(int mSize = 0); ~PrioQueue() { delete []q; } bool IsEmpty() const { return n == 0; } // 優先隊列為空返回true bool IsFull() const { return n == maxSize; } // 優先隊列為滿返回true void Append(const T& x); // 優先隊列中添加值為x的元素 void Serve(T& x); // 優先隊列中彈出隊列中優先權最高的元素, 并賦值給x private: void AdjustDown(int r, int j); // 向下調整 void AdjustUp(int j); // 向上調整 void Print(); T* q; int n, maxSize; /* data */ }; template <class T> void PrioQueue<T>::Print() { for(int i = 0; i < n; ++i) cout << q[i] << "\t"; cout << endl; } template <class T> PrioQueue<T>::PrioQueue(int mSize) { maxSize = mSize; n = 0; q = new T[maxSize]; } template <class T> void PrioQueue<T>::AdjustUp(int j) { int i = j; T tmp = q[i]; while(i > 0 && tmp < q[(i - 1) / 2]) { q[i] = q[(i - 1) / 2]; i = (i - 1) / 2; } q[i] = tmp; Print(); } template <class T> void PrioQueue<T>::Append(const T& x) { assert(!IsFull()); q[n++] = x; AdjustUp(n - 1); } template <class T> void PrioQueue<T>::Serve(T& x) { assert(!IsFull()); x = q[0]; q[0] = q[--n]; AdjustDown(0, n - 1); } template <class T> void PrioQueue<T>::AdjustDown(int r, int j) { int child = 2 * r + 1; T tmp = q[r]; while(child <= j) { if(child < j && q[child] > q[child + 1]) child++; if(tmp <= q[child]) break; q[(child - 1) / 2] = q[child]; child = 2 * child + 1; } q[(child - 1) / 2] = tmp; Print(); } int main(int argc, char const *argv[]) { PrioQueue<int> pq(8); // 實現過程 pq.Append(71); pq.Append(74); pq.Append(2); pq.Append(54); pq.Append(93); pq.Append(52); pq.Append(28); int i; cout << endl; pq.Serve(i); pq.Serve(i); return 0; } ~~~