优先队列与堆

题目: 优先队列与堆
学生姓名: 李楠20100820210 李双20100820211 李桐20100820212
专业班级:通信工程二班
背景
优先级队列（priority queue）就是遵循两个排序规则的集合。

首先，具有高优先级的项目在先。

第二，具有相同优先级的项目使用先进先出方法来确定其排序。

用到优先队列的地方：凡是需要取出集合中最值元素的地方。

●构建霍夫曼编码
构建霍夫曼编码需要找到结点集合中频率最小的两个结点。

然后合并结点插入到集
合。

依次循环。

●一些任务调度算法
比如操作系统中线程调度算法，有的是按照优先级来调度的，每次都执行优先级最
高的线程。

●合并n个有序文件为一个有序文件。

首先把n个有序文件的第一个元素都提取出来，放入优先队列中，然后取出最小的
元素。

然后再插入元素到优先队列，在取出最小元素。

●由于优先队列内部一般是采用堆实现的，所以，所有适用于堆得算法，都适用于优
先队列。

比如，排序，找中位数，找最大的K个数等。

可以以很多方式实现优先队列，比如链表、二叉查找树。

但从时空复杂度优化的角度来看，对于优先队列最普遍的实现是堆。

堆的意义就在于：最快的找到最大/最小值，在堆结构中插入一个值重新构造堆结构，取走最大/最下值后重新构造堆结构，其时间复杂度为O(logN)，而其他方法最少为O(N)。

问题描述
假设某医生看病人的顺序是由病人的病情严重程度来决定。

护士按照所有病人来医院的时间顺序给病人编号ID，依次为1，2，3，…，n；并且根据病人的病情严重程度设置Priority 值，病越重，Priority的值越小。

当医生开始工作时，护士根据病人的Priority值，由小到大依次安排病人看病。

试为护士编写程序安排病人看病的先后次序。

一、需求分析
1．本程序要求采用利用最小值堆实现一个优先队列。

2．利用优先队列存入所有病人的信息（编号和病情严重程度）。

最后利用优先队列获得病人看病的次序。

3．在Dos界面输出病人看病的次序。

4．测试数据
输入
115
2 3
3 5
420
510
－1 －1
输出
2
3
5
1
4
二、概要设计
抽象数据类型
为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。

算法的基本思想
根据用户输入利用数组结构建树的方法建立最小值堆。

程序的流程
程序由三个模块组成：
（1）输入模块：完成多组两个正整数的输入，存入结构体heapnode（堆结点）中。

（2）计算模块：将用户的输入存入堆结点中利用siftdown函数调整为最小值堆。

（3）输出模块：屏幕上显示最小值排序。

三、详细设计
物理数据类型
typedef struct heapnode //堆的结点
{
int num;
int tag;
} heapnode;
typedef struct minheap //最小值堆
{
heapnode heap[MAX];
int currentsize;
} minheap;
算法的具体步骤
#include<cstdlib>
#include<cstdio>
#include<iostream>
using namespace std;
#define MAX 50
typedef struct heapnode //堆的结点
{
int num;
int tag;
} heapnode;
typedef struct minheap //最小值堆
{
heapnode heap[MAX];
int currentsize;
} minheap;
void siftdown(minheap& H , int i , int m) //从结点i到m为止，自上而下比较，小的上浮继续向下一层比较
{
int temp1=H.heap[i].num;
int temp2=H.heap[i].tag; //j是i的左子女位置
for(int j=2*i+1 ; j<=m ; j=2*j+1) //检查是否到最后位置
{
if(j<m&&H.heap[j].num>H.heap[j+1].num) //j指向两子女中小者
j++;
if(temp1<=H.heap[j].num) //小则不作调整
break;
else //小者上移，i下降
{
H.heap[i].num=H.heap[j].num;
H.heap[i].tag=H.heap[j].tag;
i=j;
}
}
H.heap[i].num=temp1; //回放temp中暂存元素
H.heap[i].tag=temp2;
}
void creatMinHeap(minheap&H , int n) //建堆
{
H.currentsize=n;
int currentpos=(H.currentsize-2)/2; //找最初调整位置，最后分支节点
while(currentpos>=0) //自底向上逐步扩大形成堆
{
siftdown(H , currentpos , H.currentsize-1);//局部自上而下筛选
currentpos--; //再换前一个分支接点}
}
bool Remove(minheap&H) //删除最小值
{
if(!H.currentsize) //堆空情况
return false;
H.heap[0].num=H.heap[H.currentsize-1].num; //最后元素填补到根节点
H.heap[0].tag=H.heap[H.currentsize-1].tag;
H.currentsize--;
siftdown(H , 0 , H.currentsize-1); //自上向下调正为堆
return true;
}
int main()
{
minheap H;
int a,b;
int i=0;
while(cin>>a>>b&&(a!=-1)&&(b!=-1))
{
H.heap[i].tag=a;
H.heap[i].num=b;
i++;
}
creatMinHeap(H , i);
while(H.currentsize>0)
{
cout<<H.heap[0].tag<<endl;
Remove(H);
}
return 0;
}
算法的时空分析
N 个结点的完全二叉树的深度为k=[)1(log 2 n ]，建树时操作执行了n/2次siftdown 算法，时间复杂度为)log (2n n O ，堆的删除算法时间复杂度为)(log
2n O ，故本程序的总时间
复杂度为)log (2n n O 。

四、测试结果
五、实验心得
李桐：通过本次试验，对堆的建立有了更深入的了解，特别是对siftdown 函数的理解。

并在
建堆中对利用数组结构建立二叉树及其父子结点的关系加强了对其的掌握程度。