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

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

优先级队列定义:优先级高的元素在队头,优先级低的元素在队尾

基于普通线性表实现优先级队列,入队和出队中必有一个时间复杂度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;
	}
	//否则下滤结束
	else
	break;	
	  //否则选择左孩子结点上滤
}

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;
	}
	else
	break;	

建堆过程可以表示为

//建堆 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(); //寻找空闲服务台,找不到返回-1
	int 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;

}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505313.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

WPF碎片

1、Style作为资源可放在控件自身资源下&#xff0c;也可以放在上级控件下如Window.Resources甚至Application.Resources下&#xff0c;但第二种方法需要加为Style添加key并通过Style"{StaticResource xxx}类似方式调用&#xff0c;而前者控件直接默认使用&#xff1b; 方法…

printf()对浮点数的四舍五入是有问题的!!!

一、问题描述 4.5四舍五入应该是5&#xff0c;8.5四舍五入应该是9 但是printf()函数以".f"和.lf打印&#xff0c;得到的却是4和8 二、问题演示 1、代码 #include<stdio.h> int main() {float f4.5;double d8.5;printf("%.f\n",f);printf("…

C语言实现猜数字游戏(有提示,限制次数版)

这次的猜数字游戏我添加了新的功能&#xff1a;为玩家添加了提示&#xff0c;以及输入数字的限制次数。 首先&#xff0c;我们的猜数字游戏需要一个菜单&#xff0c;来让玩家可以选择玩游戏还是退出游戏&#xff0c;所以我们需要开始就打印一个菜单&#xff1a; int main() {…

Linux之进程间通信

1.进程间通信的目的 数据传输&#xff1a;一个进程需要将它的数据发送给另一个进程 资源共享&#xff1a;多个进程之间共享同样的资源。 通知事件&#xff1a;一个进程需要向另一个或一组进程发送消息&#xff0c;通知它&#xff08;它们&#xff09;发生了某种事件&#xff…

谷歌商店如何绑定银行卡!通过支付宝!

完整操作视频在B站&#xff1a; https://www.bilibili.com/video/BV1zt421g7pa/?spm_id_from333.337.search-card.all.click&vd_sourceb5a2563a2e562c5165936c011dcfd0a5 谷歌商店怎么支付&#xff01; 谷歌商店主要用来购买游戏和支付app的应用&#xff0c;由于都是采…

蓝桥杯省赛刷题——题目 2656:刷题统计

刷题统计OJ链接&#xff1a;蓝桥杯2022年第十三届省赛真题-刷题统计 - C语言网 (dotcpp.com) 题目描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目&#xff0c;周六和周日每天做 b 道题目。请你帮小明计算&#xff0c;按照计划他将在第几…

P6学习:Oracle Primavera P6 OBS/责任人解析

前言 Primavera P6 EPPM 责任人用于管理 P6 企业项目组合管理 (EPPM) 系统中的项目所有权和权限。 Primavera P6 EPPM 中的所有项目都至少围绕三个结构进行组织&#xff1a;称为企业项目结构 (EPS) 的用于组织项目的结构、称为工作分解结构 (WBS) 的用于组织项目内活动的结构…

一篇讲明白 Hadoop 生态的三大部件

文章目录 每日一句正能量前言01 HDFS02 Yarn03 Hive04 HBase05 Spark及Spark Streaming关于作者推荐理由后记赠书活动 每日一句正能量 黎明时怀着飞扬的心醒来&#xff0c;致谢爱的又一天&#xff0c;正午时沉醉于爱的狂喜中休憩&#xff0c;黄昏时带着感恩归家&#xff0c;然后…

ALPHA开发板上PHY网络芯片LAN8720:常用的几个寄存器功能

一. 简介 正点原子的开发板 ALPHA开发板&#xff0c;有线网络硬件方案所使用的也是最常用的一种方案&#xff0c;IMX6ULL芯片内部是自带 MAC网络芯片的&#xff0c;所以&#xff0c;也就是采用 "SOC内部集成网络MAC外设 PHY网络芯片方案"。 前面一篇文章简单了解了…

【python从入门到精通】-- 第三战:输入输出 运算符

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…

Android动画(一):视图动画

文章概览 1 Android动画概述1.1 动画的分类1.2 视图动画与属性动画的区别 2 视图动画View Animation2.1 补间动画Tween Animation2.1.1 XML中用标签实现补间动画2.1.2 代码实现补间动画 2.2 逐帧动画Frame Animation2.2.1 XML实现逐帧动画2.2.2 代码实现逐帧动画 本系列将介绍以…

MySQL 之 数据库操作 及 表操作

&#x1f389;欢迎大家观看AUGENSTERN_dc的文章(o゜▽゜)o☆✨✨ &#x1f389;感谢各位读者在百忙之中抽出时间来垂阅我的文章&#xff0c;我会尽我所能向的大家分享我的知识和经验&#x1f4d6; &#x1f389;希望我们在一篇篇的文章中能够共同进步&#xff01;&#xff01;&…

(一)kafka实战——kafka源码编译启动

前言 本节内容是关于kafka消息中间键的源码编译&#xff0c;并通过idea工具实现kafka服务器的启动&#xff0c;使用的kafka源码版本是3.6.1&#xff0c;由于kafka源码是通过gradle编译的&#xff0c;以及服务器是通过scala语言实现&#xff0c;我们要预先安装好gradle编译工具…

了解XSS和CSRF攻击与防御

什么是XSS攻击 XSS&#xff08;Cross-Site Scripting&#xff0c;跨站脚本攻击&#xff09;是一种常见的网络安全漏洞&#xff0c;它允许攻击者在受害者的浏览器上执行恶意脚本。这种攻击通常发生在 web 应用程序中&#xff0c;攻击者通过注入恶意脚本来利用用户对网站的信任&…

springboot论坛管理系统

论坛管理系统 摘要&#xff1a; 在社会快速发展的影响下&#xff0c;论坛管理系统继续发展&#xff0c;使论坛管理系统的管理和运营比过去十年更加信息化。依照这一现实为基础&#xff0c;设计一个快捷而又方便的网上论坛管理系统是一项十分重要并且有价值的事情。对于传统的论…

Linux简单命令

Linux简单命令 本文是自己学习过程中的一些记录&#xff0c;对于熟悉的部分并未全部列出&#xff0c;仅供参考 内核架构图 一切皆是文件 常用的linux命令 用户的管理 修改密码&#xff1a;passwd 创建一个新用户&#xff1a;useradd 用户名给新用户设置密码&#xff1a;…

【Linux】详解文件系统以及周边知识

一、磁盘的基本知识 磁盘中可以被划分成一个一个的环&#xff0c;每个环都是一个磁道。每个磁道又可以被均分成一个一个的扇区&#xff0c;扇区是磁盘IO的基本单位&#xff08;想要修改扇区中的一个比特位就必须把该扇区的全部比特位都加载到内存中&#xff09;。磁盘中的盘面&…

C++入门(函数重载、缺省参数、引用)

目录 函数重载函数重载的概念函数重载的原理----名字的修饰 缺省参数缺省参数的分类 引用引用的特征使用场景 函数重载 函数重载的概念 在自然语言中&#xff0c;相同的一个词可能有多重含义&#xff0c;人们可以通过上下文来判断这个词的具体意思&#xff0c;在C中也存在这种…

虚函数和纯虚函数

虚函数 被virtual修饰的成员函数称为虚函数 定义一个函数为虚函数&#xff0c;是为了使用基类指针调用子类函数。虚函数&#xff0c;不代表函数不被实现。只有纯虚函数才不被实现&#xff0c;纯虚函数定义了一个接口&#xff0c;起到规范的作用。 #include <iostream>…

快讯!TiDB v8 发版!超硬核 v8 引擎!

TiDB 是 PingCAP 公司自主设计、研发的开源分布式关系型数据库&#xff0c;是一款同时支持在线事务处理与在线分析处理 (Hybrid Transactional and Analytical Processing, HTAP) 的融合型分布式数据库产品。 具备水平扩容或者缩容、金融级高可用、实时 HTAP、云原生的分布式数…