使用数组作为存储方式的最小优先级队列。
Insert()操作直接把元素item加入到优先级队列的队尾，然后进行调整，把插入元素按它的优先权调整到适当位置，使得队列中所有元素都按照其优先权大小，
从小到大形成一个有序序列。最好情况是新插入元素优先权最大，一个元素都不用移动；最差情况是新插入元素的优先权最小， 所有元素都要移动，移动次数达到n+1次，其时间复杂度为O(n)；
RemoveMin()操作在删除队头元素后，为保持队列有序，需要把所有后续n-1个元素前移，时间复杂度为O(n)
#pragma once
#include
using namespace std;
const int PQsize = 50;
template
class PQueue
{
public:
PQueue(int sz = PQsize);
~PQueue() { delete[] elements; }
bool Insert(const T& x); //插入函数
bool RemoveMin(T& x); //将队头元素删除
bool getFront(T& x)const; //获得队头（具有最小优先级）的元素
void makeEmpty(); //置空
bool IsEmpty()const { //判空
return count == 0 ? true : false;
}
bool IsFull()const { //判满
return count == MaxSzie ? true : false;
}
int getSize()const { //求队列元素个数
return count;
}
private:
T *elements; //优先级队列数组
int count; //当前元素个数
int MaxSzie; //队列最大可容纳个数
adjust(); //队列调整函数
};
//================================================实现=================================
template
PQueue::PQueue(int sz):MaxSzie(sz),count(0)
{
//建立一个最大具有maxsize个元素的空优先队列
elements = new T[MaxSzie];
if (elements == nullptr) {
cout << "分配内存失败！";
}
}
template
bool PQueue::Insert(const T & x)
{
//若队列不满，则将元素x插入队尾，否则出错处理
if (IsFull() == true) {
cout << "队列已满！";
return false;
}
elements[count++] = x;
adjust();
return false;
}
template
bool PQueue::RemoveMin(T & x)
{
//若队列不为空，则返回最大优先权的元素，同时将该元素删除
if (count == 0) {
return false;
}
x = elements[0];
for (int i = 1; i < count; ++i) { //将数组元素整体向前移动
elements[i - 1] = elements[i];
}
count--;
return true;
}
template
bool PQueue::getFront(T & x) const
{
//队列为空，返回FALSE，否则返回第一个元素
if (IsEmpty() == true) {
return false;
}
else {
x = elements[0];
return true;
}
}
template
void PQueue::makeEmpty()
{
count = 0;
}
template
PQueue::adjust()
{
//将队尾按其优先级大小，调整到适当位置，保持所有优先权从小到大有序
T temp = elements[count - 1];
int j;
for (j = count - 2; j >= 0; --j) {
if (elements[j] <= temp) { //找到小于等于队尾元素的第一个元素，跳出循环
break;
}
else {
elements[j + 1] = elements[j]; //将元素后移
}
}
elements[j + 1] = temp; //将队尾元素放在第一个小于等于该元素的元素后面
}
