如果定义最小值为最高优先权, 使用最小堆为例.  每次入队新元素都要向上调整, 同理, 弹出优先权最高的元素时要向下调整, 使之成为堆. 将新元素插入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; } ~~~