数据结构5

数据结构 5 优先级队列

优先级队列

结点间的关系由结点的优先级决定，而不是入队的先后顺序。

我们最先想到的是使用线性结构进行优先级队列的实现

• 如果按优先级排序
  但是入队操作复杂度达到了O(N)
• 如果按到达时间排序
  但是出队操作复杂度达到了O(N)

于是我们考虑…

二叉堆

堆是一棵完全二叉树（结构性），且满足下列2个条件之一：父结点小于等于子结点（小根堆）or 父结点大于等于子结点（大根堆）（有序性）

基于二叉堆的优先级队列
成员函数：实现队列的所有操作
数据成员：基于二叉堆的结构性（完全二叉树）可以使用顺序存储——数组

优先级队列的定义

入队enQueue的过程：

• 插入在最底层的一个空位
• 向上移动到合适的位置（向上过滤）
  和父结点进行比较
• 时间复杂度：最坏的时间性能是对数级的O(logN)，也可通过数学证明平均时间复杂度

出队deQueue的过程：

• 删除根结点
• 将最后一个结点移到根结点（保持结构性）
• 向下移动到合适的位置（向下过滤）
• 很少有能提前结束的

建堆：
方法一：在空堆中执行N次连续插入
中间不保证二叉堆结构

方法二：不考虑中间状态，保证所有元素加入后满足堆的特性
最坏情况下时间复杂度达到O(N)（在MIT6.006 1中介绍了证明）
将左子树和右子树调整成堆
对根结点调用percolateDown，以恢复堆的有序性
也就是说，对所有非叶结点向下过滤

其他堆

D-堆 “完全D叉树” O(logN)
可能用于队列太大，要放在外存中时

左堆、斜堆、二项堆——支持归并

左堆

满足堆的有序性，但平衡稍弱一些的堆，不要求是完全二叉树
npl(x)为x到不满两个孩子的节点的最短路径，即具有0个或一个孩子的结点的npl为0，npl(NULL) = -1
对每个节点x，左孩子的npl不小于右孩子的npl
显然，左堆是一棵像左倾斜的树
归并方法：将根结点稍大的堆与另一个堆的右子树归并（对于小根堆） 不会很偏
递归终止条件：当某个堆为空时，另一个堆就是归并结果。
入队、出队操作均可以用归并操作实现

斜堆

斜堆是自调整的左堆，将根结点较大的堆和另一个堆的右子树归并，然后交换左右子树（更简单，不用维护左偏值信息）

二项堆

一个二项树的集合，每个高度的二项树至多出现一次。

二项树
有序性：满足堆的有序性
结构性：高度为0的二项树是单个节点，高度为k的二项树Bk是将一棵Bk-1加到另一棵Bk-1的根上

由于元素数可以二进制表示，故堆的结构是唯一的。

归并操作：
由低到高依次归并两个优先级队列中高度相同的树。
高度相同的树归并时，将根结点大的作为根结点小的子树（小根堆）。
若由于前一次归并导致有3棵高度形同的树，则归并其中2棵。
由于N个结点最多有logN棵二项树，故时间复杂度为O(logN)。

入队操作：
将入队结点形成一棵单结点的树组成的集合，归并2个集合。
最坏情况下，原集合每个高度的树都有，则时间复杂度为O(logN)。

删除操作：
找出具有最小根值的树T
将T从原先的集合中删掉，在T中删除根结点，归并T与原先的集合。
最坏情况时间复杂度依然是O(logN)。

STL中的优先级队列

头文件：#include
类模板：priority_queue
实现方式：二叉堆

排队系统的模拟

单服务台系统 VS 多服务台系统
多服务台系统中，需要将产生的到达事件和离开事件都加入优先级队列中。