牛小飞《数据结构》6优先队列

1、优先队列（堆）,priority queue 应用于操作系统的进程调度策略中,优先队列的基本模型 优先队列的实现思考 二叉堆 优先队列的应用 小结,优先队列（堆）,优先队列的基本模型,至少允许两种操作： insert deleteMin,等价于enqueue(入队),是dequeue(出队)在优先队列中的等价操作,优先队列实现思考,链表：在表头执行插入操作O(1)，遍历该链表实现删除最小元素O(n)。 二叉查找树：deleteMin操作会损害树的平衡，使得右子树加重。另外，二叉平衡树支持更多的但在优先队列中不需要的操作。 二叉堆,二叉堆(binary heap),堆的定义 二叉堆的性质：结构性

2、质、堆序性质 二叉堆的操作：insert、deleteMin、buildHeap 二叉堆的应用：选择问题、事件模拟,堆的定义,堆是满足下列性质的数列r1, r2, ，rn：,或,(小顶堆),(大顶堆),若将此序列所存储的一维数组R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树： 树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。,堆的定义,小顶堆： 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。 大顶堆： 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。 注意： 堆中任一子树亦是堆。 以上讨

3、论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。,堆的定义,（13，38，27，50，76，65，49，97）,（96，83，27，38，11，9）,小顶堆,大顶堆,二叉堆的结构性质,二叉堆是一棵完全二叉树。所以，可以用数组来表示。,0 1 2 3 4 5 6 7 8 9 10 11 12 13,对于数组中任一位置i上的元素， 其左孩子在位置2i上，右孩子在 左孩子后的位置(2i+1)上。它的 父节点在i/2的位置上。,图中二叉堆大小的限界是13个元素。,在一个二叉堆中，对于每一个节点X，X的父亲中的关键字小于（或等于）X中的关键字，根节点除外。,二叉堆的堆序性质,二叉堆,

4、非二叉堆,根据二叉堆的堆序性质 最小元总可以在根处找到,所有的操作都要保证堆序性质。,二叉堆的操作insert,插入操作的基本思想： 创建一个空穴，再将空穴上冒，这种策略叫上滤(percolate up)。,二叉堆的操作insert,31,21,14,public void insert(AnyType x) if(currentSize=array.length-1) enlargeArray(array.length*2+1); int hole=+currentSize; for(;hole1 ,二叉堆的操作insert,二叉堆的操作deleteMin,deleteMin(删除最小元)操

5、作的基本思想： 即删除根节点。在根节点建立一个空穴，然后将堆中最后一个元素X移动到该堆的某个地方后仍构成二叉堆这种策略叫下滤(percolate down)或筛选,二叉堆的操作deleteMin,14,19,26,31,public AnyType deleteMin() if(isEmpty() throw new UnderflowException(); AnyType minItem=findMin(); array1=arraycurrentSize-; percolateDown(1); return minItem; ,二叉堆的操作deleteMin,private void p

6、ercolateDown(int hole) int child; AnyType tmp=arrayhole; for(; hole*2=currentSize; hole=child) child=hole*2; if(child!=currentSize ,二叉堆的操作deleteMin,二叉堆的操作buildHeap,构建堆buildHeap的基本思想： 从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复下滤(筛选)。,将含8个元素的无序序列 (59，97，56，50，53，65，62，76)调整成小顶堆。,1.先将无序序列建立完

7、全二叉树,二叉堆的操作buildHeap,堆排序建立堆过程,2.按照建堆思想，将(59，97，56，50，53，65，62，76)调整成小顶堆。,public BinaryHeap(AnyType items) currentSize=items.length; array=(AnyType) new Comparable(currentSize+2)*11/10; int i=1; for(AnyType item:items) arrayi+=item; buildHeap( ); ,二叉堆的操作buildHeap,二叉堆的操作buildHeap,private void buildHeap( ) for(int i=currentSize/2;i0;i-) percolateDown(i); ,优先队列的应用选择问题,输入N个元素及一个整数k，这N个元素