数据结构课件-第06章.pptx

数据结构俞勇、张铭、陈越、韩文弢上海交通大学、北京大学、浙江大学、清华大学

优先级队列第6章韩文弢清华大学

6.1问题引入6.2优先级队列的定义6.3二叉堆6.4多叉堆6.5可并堆6.6优先级队列应用6.7拓展延伸6.8应用场景

6.1问题引入：带优先级的服务处理问题：第3章介绍的队列能够按先到先得的方式来处理，但实际问题中（例如医院或者银行）还有可能需要考虑加急的情况，更一般地说就是优先级。如何按优先级进行处理？关键：出队的顺序需要由元素本身的优先级来决定，而不是进队的顺序。

6.2优先级队列的定义优先级队列是一种特殊的队列。与普通队列相比，相同点：都支持进队和出队操作。不同点：优先级队列的出队顺序按事先规定的优先级顺序进行。ADTPriorityQueue{数据对象：????元素取自全集U的可重集合E，表示优先级队列中包含的元素。数据关系：????全集U中的元素须满足严格弱序。基本操作：（省略初始化、销毁、清除内容、判断为空、查询元素个数等操作）????Insert(pq,x)：在优先级队列pq中插入元素x。????ExtractMin(pq)：从优先级队列pq中删除优先级最高（也就是值最小）的元素，并返回。????PeekMin(pq)：返回优先级队列pq中优先级最高的元素（元素仍然保留在优先级队列中）。}

优先级队列的实现优先级队列可以用线性表来实现。然而，使用线性表实现时出队操作需要将当前优先级队列中的所有元素都检查一遍，从而找到优先级最高的元素。假设优先级队列中元素个数为n，这种实现下出队操作的复杂度是O(n)，效率较低。一般会使用二叉堆等更加高效的数据结构来实现优先级队列。

6.3二叉堆二叉堆是一种常见的堆，常用来实现优先级队列。二叉堆最早由J.W.J.Williams于1964年提出，作为支持堆排序的一种数据结构。

6.3.1二叉堆的定义二叉堆是父结点元素和子结点元素满足一定大小关系的完全二叉树。根据条件不同，可分为最小堆和最大堆。最小堆：如果完全二叉树T中的所有父子结点对都有父结点的元素不大于子结点的元素，则称T为最小堆。最大堆：如果完全二叉树T中的所有父子结点对都有父结点的元素不小于子结点的元素，则称T为最大堆。（最小堆和最大堆的区别只在于父子结点元素之间的大小关系）为简便起见，本章中的二叉堆（也包括其他种类的堆）都以最小堆为例进行讲解，最大堆的情况可类推得到。

6.3.1二叉堆的定义?结点结点下标123456

6.3.2二叉堆的操作二叉堆的基本操作是堆元素的上调和下调。（这里的“上”和“下”是指用一般习惯画出二叉堆的树表示后元素在调整过程中的走向）在上调和下调操作的基础上，可实现堆元素的插入、删除，以及建堆操作。设数组h.data[]中保存着二叉堆中的元素。在对二叉堆进行操作的过程中，可能会出现不满足二叉堆性质的时刻，为表述方便，仍用堆来称呼此时的状态。

二叉堆的上调操作上调操作：如果堆中某结点i小于其父结点p，此时可以交换结点i和结点p的元素，也就是把结点i沿着堆的这棵树往“上”调整。此时，再看新的父结点与它的大小关系。重复该过程，直到结点i被调到根结点位置或者和新的父结点大小关系满足条件。如图演示了一次二叉堆的上调操作的过程，元素1从开始的叶结点位置一直调整到了根结点。

二叉堆的上调操作在实现时，可以通过以下方法避免交换，从而减少赋值操作的次数。SiftUp先将结点i的元素保存在临时变量中，随着调整将父结点的元素往“下”移动，最后再将原来结点i的元素填入合适的位置。由此得到上调操作的算法如下：对于上调操作而言，循环的次数不会超过树的高度，因此时间复杂度为O(logn)。算法6-1：二叉堆的上调操作SiftUp(h,i)输入：堆h和上调起始位置i输出：上调后满足堆性质的helem←h.data[i]whilei1且elemh[i/2]do//当前结点小于其父结点|h.data[i]←h.data[i/2]//将i的父结点元素下移|i←i/2//i指向原结点的父结点，即向上调整endh.data[i]←elem

二叉堆的下调操作下调操作：如果堆中某结点i大于其子结点，则要将其向“下”调整。调整时需要注意，对于有两个子结点的情况，如果两个子结点均小于结点i，交换时应选取它们中的较小者，只有这样才能保证调整之后三者的关系能够满足堆的性质。重复该过程，直到结点i被调到叶结点位置或者和新的子结点大小关系满足条件。如图演示了一次二叉堆的下调操作的过程，元素7从开始