当前位置：首页 > news >正文

数据结构——优先级队列及多服务台模拟系统的实现

news 来源：原创 2024/5/17 16:28:49

一、优先级队列的定义和存储

优先级队列定义：优先级高的元素在队头，优先级低的元素在队尾

基于普通线性表实现优先级队列，入队和出队中必有一个时间复杂度O(n),基于二叉树结构实现优先级队列，能够让入队和出队时间复杂度都为O(logn），这种基于树状结构的优先级队列也称为二叉堆。当根结点为最大元素时，称为最大化堆或大顶堆;当根结点为最小元素时，称为最小化堆或小顶堆。二叉堆是有序的完全二叉树，使用顺序存储，留出数组第一个位置作为哑结点，如图所示：

二、优先级队列的运算实现

先学习优先级队列的两大核心运算：入队和出队，之后再介绍如何建堆。下面以小顶堆为例分析。

2.1 入队：上滤插入

在原有的二叉堆上插入新元素，同时使其维持有序性，可以通过“上滤”实现。第一步是寻找新元素应插入的位置，第二步是插入新元素，时间复杂度为O(logn）
//先将新元素放在二叉堆最底部
int hole=++currentlength;
//与父结点比较，决定是否交换（实际上不需要交换，因为新元素不一定到达最终插入位置）,条件：比父结点值小,上滤过程持续进行，设置循环;
//循环结束条件:到达堆顶(hole=1)或已到达最终插入位置
while(hole>1&&x<array[hole/2])
{array[hole]=array[hole/2]; //父结点下移hole/=2; //更新新元素位置
}
//插入元素
array[hole]=x;

2.2 出队：下滤删除

现在要删除队头元素，也就是堆顶元素，简单的想法是和孩子节点比较，选择其中较小的上滤，可这样可能会破坏二叉堆完全二叉树的结构[比如1 3 2 4 5删除后2 3 null 45]，为了维持完全二叉树的结构，我们需要考虑为堆最后一个结点重新寻找位置。如图所示，将最后一个节点放在堆顶再下滤，就能实现删除堆顶元素并使二叉树结点数量减一。[比如1 3 2 4 5->

5 3 2 4->2 3 5 4]，时间复杂度为O(logn）
//把最后一个元素放在堆顶
tmp=array[1]=array[currentlength--];
hole=1;
//叶子结点条件 2i>n,非叶子结点条件：2i<=n
while(2*hole<=currentlength){//选择较小子节点child=2*hole;if(2*hole!=currentlength) if(array[child]>array[child+1])  child++;//下滤if(tmp>array[child]) {array[hole]=array[child];hole=child;}//否则下滤结束elsebreak;	//否则选择左孩子结点上滤
}

2.3 建堆

在构造函数中传入数据数组初始化二叉堆，最简单的想法是对N个元素执行N次入队操作，每次入队后对维持二叉堆有序性，时间复杂度O(nlogn);如何提升时间效率呢，可以先用原始数据初始化二叉堆，再从最后一个非叶节点开始到第一个结点，依次执行下滤操作，这样调用percolateDown（i）时保证结点i的所有自堆都满足有序性，这样自下往上，从局部有序最后抵达全局有序，可以证明这种建堆方式时间复杂度为O（n）。

对2.2中的代码略微修改容易得到下滤函数：
//下滤函数 precolateDown实现
tmp=array[i];
hole=i;
while(2*hole<=currentlength){child=2*hole;if(2*hole!=currentlength) if(array[child]>array[child+1])  child++;if(tmp>array[child]) {array[hole]=array[child];hole=child;}elsebreak;	
建堆过程可以表示为
//建堆 buildHeap 实现
for(int i=currentlength/2;i>0;i--){precolateDown(i);
}

三、 STL中的优先级队列

类模板名：priority_queue

头文件：queue

定义：priority<elemtype,base container(默认 vector),(默认大顶堆，添加谓词greater<int>则定义小顶堆)>

成员函数：

void push() 入队

void pop() 出队

Elemtype top() 获取队头元素

void clear() 清空

bool empty() 判空

四、D堆

D堆就是D叉树，由于生成的堆更矮，入队的时间复杂度为 $O(log_{D}N)$ ,比二叉堆更加优越。

但出队时就不一样了，由于需要比较子结点，若采用最简单的选择算法，则时间复杂度为 $O(Nlog_{D}N)$ ，因此D堆适用于插入操作比删除操作多非常多的场景。

五、归并优先级队列（了解）

归并：即合并两棵有序树，在前面我们做过合并二叉树的题目，归并可通过递归实现

5.1 左堆

这里的nql容易通过递归实现，参考二叉树中刷题中的类似题目。

5.2 斜堆

5.3 二项堆

二项堆和二进制有很大相似性，归并的过程也像二进制加法

六、多服务台排队系统模拟

#include<queue>
#include<ctime>
#include<cstdlib>
#include<iostream>
using namespace std;class simulator {  //模拟类
private:enum IO { IN, OUT };struct event {//事件类型IO io; //事件性质：顾客到达/顾客离开int serviceNo; //服务柜台编号int eventTime; //事件时间int customNo; //顾客编号};struct compare {bool operator()(const event& e1, const event& e2){return e1.eventTime > e2.eventTime;}};int* service; //服务台priority_queue<event, deque<event>, compare> Main; //处理事件队列，按照事件时间优先级排列，事件时间越早，优先级越高queue<event> Wait; //排队队列int customNum; //顾客数量int serviceNum; //服务台数量int serviceTimeMax; //最长服务时间int serviceTimeMin; //最短服务时间int arriveLow;//允许到达最早时间int arriveHigh; //允许到达最晚时间int searchFree(); //寻找空闲服务台,找不到返回-1int currentTime; //模拟中当前时间
public:simulator(int sTMax, int sTMin, int cusNum, int serNum,int arL,int arH) {customNum = cusNum;serviceNum = serNum;serviceTimeMax = sTMax;serviceTimeMin = sTMin;arriveLow = arL;arriveHigh = arH;service = new int[serNum] {0};//将所有服务台置于空闲状态(0)currentTime = 0;};void Simulation(); //模拟整个排队过程
};int simulator::searchFree()
{for (int i = 0; i < serviceNum; i++){if (service[i]==0) return i;}return -1;
}void simulator::Simulation()
{//产生顾客的服务时间，并存入队列event* Eve;Eve=new event[customNum];for (int i = 0; i < customNum; i++){Eve[i].io = IN;Eve[i].eventTime = arriveLow + rand() % (arriveHigh - arriveLow + 1);Eve[i].serviceNo = -1; //未服务Eve[i].customNo = i;Main.push(Eve[i]);}//开始处理事件while (!Main.empty()){int index;event tmp = Main.top();Main.pop();currentTime = tmp.eventTime; //更新当前时间switch (tmp.io) {case IN:  //处理到达事件if ((index=searchFree())!=-1) //存在空闲服务台,让顾客前往该服务台{service[index] = 1;tmp.serviceNo = index;//将时间修改为离开事件，并随机生成其业务服务时间，修改事件时间，重新入队tmp.io = OUT;int Stime = serviceTimeMin + rand() % (serviceTimeMax - serviceTimeMin + 1);tmp.eventTime += Stime;Main.push(tmp);cout << "当前时间：" << currentTime << endl;cout << "服务台" << index << "正在服务顾客" << tmp.customNo << "，服务时长预计" << Stime << "分钟" << endl;}else {  //不存在空闲服务台，让顾客排队等待Wait.push(tmp);}break;case OUT:int NO = tmp.serviceNo;cout << "当前时间：" << currentTime << endl;cout << "服务台" << NO << "完成服务顾客" << tmp.customNo << endl;//排队队列非空,让排队队列第一个人接受空出服务台服务if (!Wait.empty()){event tmp2 = Wait.front();Wait.pop();int Stime = serviceTimeMin + rand() % (serviceTimeMax - serviceTimeMin + 1);tmp2.eventTime = currentTime+Stime;tmp2.io = OUT;tmp2.serviceNo = NO;Main.push(tmp2);cout << "当前时间：" << currentTime << endl;cout << "服务台" << NO << "正在服务顾客" << tmp2.customNo << "，服务时长预计" << Stime << "分钟" << endl;}else {service[NO] = 0;}break;}}}int main()
{srand(time(NULL));int sTMax, sTMin, cusNum, serNum, arL, arH;cout << "输入柜台数:" << endl;cin >> serNum;cout << "输入顾客数:" << endl;cin >> cusNum;cout << "输入服务时间下界和上界(单位：分钟)" << endl;cin >> sTMin >> sTMax;cout << "输入到达时间下界和上界(单位：分钟)" << endl;cin >> arL >> arH;simulator MySim(sTMax, sTMin, cusNum, serNum,arL,arH);MySim.Simulation();return 0;}