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

优先队列（堆）,priorityqueue应用于操作系统的进程调度策略中,优先队列的基本模型优先队列的实现思考二叉堆优先队列的应用小结,优先队列（堆）,优先队列的基本模型,至少允许两种操作：insertdeleteMin,等价于enqueue(入队),是dequeue(出队)在优先队列中的等价操作,优先队列实现思考,链表：在表头执行插入操作O(1)，遍历该链表实现删除最小元素O(n)。二叉查找树：deleteMin操作会损害树的平衡，使得右子树加重。另外，二叉平衡树支持更多的但在优先队列中不需要的操作。二叉堆,二叉堆(binaryheap),堆的定义二叉堆的性质：结构性质、堆序性质二叉堆的操作：insert、deleteMin、buildHeap二叉堆的应用：选择问题、事件模拟,堆的定义,堆是满足下列性质的数列r1,r2,，rn：,或,(小顶堆),(大顶堆),若将此序列所存储的一维数组R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。,堆的定义,小顶堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。大顶堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆(BinaryHeap)，类似地可定义k叉堆。,堆的定义,（13，38，27，50，76，65，49，97）,（96，83，27，38，11，9）,小顶堆,大顶堆,二叉堆的结构性质,二叉堆是一棵完全二叉树。所以，可以用数组来表示。,012345678910111213,对于数组中任一位置i上的元素，其左孩子在位置2i上，右孩子在左孩子后的位置(2i+1)上。它的父节点在i/2的位置上。,图中二叉堆大小的限界是13个元素。,在一个二叉堆中，对于每一个节点X，X的父亲中的关键字小于（或等于）X中的关键字，根节点除外。,二叉堆的堆序性质,二叉堆,非二叉堆,根据二叉堆的堆序性质最小元总可以在根处找到,所有的操作都要保证堆序性质。,二叉堆的操作insert,插入操作的基本思想：创建一个空穴，再将空穴上冒，这种策略叫上滤(percolateup)。,二叉堆的操作insert,31,21,14,publicvoidinsert(AnyTypex)if(currentSize=array.length-1)enlargeArray(array.length*2+1);inthole=+currentSize;for(;hole1,二叉堆的操作insert,二叉堆的操作deleteMin,deleteMin(删除最小元)操作的基本思想：即删除根节点。在根节点建立一个空穴，然后将堆中最后一个元素X移动到该堆的某个地方后仍构成二叉堆这种策略叫下滤(percolatedown)或筛选,二叉堆的操作deleteMin,14,19,26,31,publicAnyTypedeleteMin()if(isEmpty()thrownewUnderflowException();AnyTypeminItem=findMin();array1=arraycurrentSize-;percolateDown(1);returnminItem;,二叉堆的操作deleteMin,privatevoidpercolateDown(inthole)intchild;AnyTypetmp=arrayhole;for(;hole*20;i-)percolateDown(i);,优先队列的应用选择问题,输入N个元素及一个整数k，这N个元素的集可以是全序集。该选择问题是要找出第k个最大元素。当k