《2022年优先队列与堆参照 .pdf》由会员分享,可在线阅读,更多相关《2022年优先队列与堆参照 .pdf(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构课程实验指导书 1 题目: 优先队列与堆学生姓名 : 李楠20100820210 李双20100820211 李桐 20100820212 专业班级 : 通信工程二班背景优先级队列( priority queue )就是遵循两个排序规则的集合。首先,具有高优先级的项目在先。第二,具有相同优先级的项目使用先进先出方法来确定其排序。用到优先队列的地方:凡是需要取出集合中最值元素的地方。构建霍夫曼编码构建霍夫曼编码需要找到结点集合中频率最小的两个结点。然后合并结点插入到集合。依次循环。一些任务调度算法比如操作系统中线程调度算法,有的是按照优先级来调度的,每次都执行优先级最高的线程。合并 n
2、个有序文件为一个有序文件。首先把 n 个有序文件的第一个元素都提取出来,放入优先队列中,然后取出最小的元素。然后再插入元素到优先队列,在取出最小元素。由于优先队列内部一般是采用堆实现的,所以, 所有适用于堆得算法,都适用于优先队列。比如,排序,找中位数,找最大的K 个数等。可以以很多方式实现优先队列,比如链表、 二叉查找树。 但从时空复杂度优化的角度来看,对于优先队列最普遍的实现是堆。堆的意义就在于:最快的找到最大/最小值,在堆结构中插入一个值重新构造堆结构,取走最大/最下值后重新构造堆结构,其时间复杂度为O(logN) ,而其他方法最少为O(N) 。问题描述假设某医生看病人的顺序是由病人的病
3、情严重程度来决定。护士按照所有病人来医院的时间顺序给病人编号ID ,依次为 1,2,3,n;并且根据病人的病情严重程度设置Priority值,病越重, Priority 的值越小。当医生开始工作时,护士根据病人的Priority 值,由小到大依次安排病人看病。试为护士编写程序安排病人看病的先后次序。一、需求分析1 本程序要求采用利用最小值堆实现一个优先队列。2 利用优先队列存入所有病人的信息(编号和病情严重程度)。最后利用优先队列获得病人看病的次序。3 在 Dos 界面输出病人看病的次序。4 测试数据输入115 23 35 420 510 1 1 输出2 3 5 名师资料总结 - - -精品资
4、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 5 页 - - - - - - - - - 数据结构课程实验指导书 2 1 4 二、概要设计抽象数据类型为实现上述程序的功能,应以整数存储用户的输入,以及计算出的结果。算法的基本思想根据用户输入利用数组结构建树的方法建立最小值堆。程序的流程程序由三个模块组成:(1)输入模块:完成多组两个正整数的输入,存入结构体heapnode(堆结点)中。(2)计算模块:将用户的输入存入堆结点中利用siftdown 函数调整为最小值堆。(3)输出模块:屏幕上显示最小值排
5、序。三、详细设计物理数据类型typedef struct heapnode / 堆的结点 int num; int tag; heapnode; typedef struct minheap /最小值堆 heapnode heapMAX; int currentsize; minheap; 算法的具体步骤#include #include #include using namespace std; #define MAX 50 typedef struct heapnode / 堆的结点 int num; int tag; heapnode; typedef struct minheap /最
6、小值堆 heapnode heapMAX; int currentsize; minheap; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 5 页 - - - - - - - - - 数据结构课程实验指导书 3 void siftdown(minheap& H , int i , int m) /从结点 i 到 m 为止,自上而下比较,小的上浮继续向下一层比较 int temp1=H.heapi.num; int temp2=H.heapi.tag; /j 是 i 的
7、左子女位置for(int j=2*i+1 ; j=m ; j=2*j+1) /检查是否到最后位置 if(jH.heapj+1.num) /j指向两子女中小者j+; if(temp1=0) /自底向上逐步扩大形成堆 siftdown(H , currentpos , H.currentsize-1);/局部自上而下筛选currentpos-; /再换前一个分支接点 bool Remove(minheap&H) /删除最小值 if(!H.currentsize) /堆空情况return false; H.heap0.num=H.heapH.currentsize-1.num; /最后元素填补到根节
8、点H.heap0.tag=H.heapH.currentsize-1.tag; H.currentsize-; siftdown(H , 0 , H.currentsize-1); /自上向下调正为堆名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 5 页 - - - - - - - - - 数据结构课程实验指导书 4 return true; int main() minheap H; int a,b; int i=0; while(cinab&(a!=-1)&(b!=-
9、1) H.heapi.tag=a; H.heapi.num=b; i+; creatMinHeap(H , i); while(H.currentsize0) coutH.heap0.tagendl; Remove(H); return 0; 算法的时空分析N 个结点的完全二叉树的深度为k=)1(log2n,建树时操作执行了n/2 次 siftdown 算法,时间复杂度为)log(2nnO,堆的删除算法时间复杂度为)(log2nO,故本程序的总时间复杂度为)log(2nnO。四、测试结果五、实验心得李桐: 通过本次试验, 对堆的建立有了更深入的了解,特别是对 siftdown 函数的理解。 并在名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 5 页 - - - - - - - - - 数据结构课程实验指导书 5 建堆中对利用数组结构建立二叉树及其父子结点的关系加强了对其的掌握程度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 5 页 - - - - - - - - -
限制150内