优先队列ADT_PrioQueue
最后更新于：2022-04-01 20:51:30
如果定义最小值为最高优先权, 使用最小堆为例.
每次入队新元素都要向上调整, 同理, 弹出优先权最高的元素时要向下调整, 使之成为堆.
将新元素插入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 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
void PrioQueue::Print()
{
for(int i = 0; i < n; ++i)
cout << q[i] << "\t";
cout << endl;
}
template
PrioQueue::PrioQueue(int mSize)
{
maxSize = mSize;
n = 0;
q = new T[maxSize];
}
template
void PrioQueue::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
void PrioQueue::Append(const T& x)
{
assert(!IsFull());
q[n++] = x;
AdjustUp(n - 1);
}
template
void PrioQueue::Serve(T& x)
{
assert(!IsFull());
x = q[0];
q[0] = q[--n];
AdjustDown(0, n - 1);
}
template
void PrioQueue::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 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;
}
~~~
';