《牛小飞《数据结构》6优先队列.ppt》由会员分享,可在线阅读,更多相关《牛小飞《数据结构》6优先队列.ppt(24页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、优先队列(堆)优先队列(堆)npriority queuen应用于操作系统的进程调度策略中应用于操作系统的进程调度策略中优先队列的基本模型优先队列的基本模型优先队列的实现思考优先队列的实现思考二叉堆二叉堆优先队列的应用优先队列的应用小结小结优先队列(堆)优先队列(堆)优先队列的基本模型优先队列的基本模型优先队列优先队列插入插入删除最小者删除最小者至少允许两种操作:至少允许两种操作:insertdeleteMin等价于等价于enqueue(入队入队)是是dequeue(出队出队)在优先队列中的等价在优先队列中的等价操作操作优先队列实现思考优先队列实现思考n链表:链表:在表头执行插入操作在表头执行
2、插入操作O(1),遍历该链表实,遍历该链表实现删除最小元素现删除最小元素O(n)。n二叉查找树:二叉查找树:deleteMin操作会损害树的平衡,操作会损害树的平衡,使得右子树加重。另外,二叉平衡树支持更多使得右子树加重。另外,二叉平衡树支持更多的但在优先队列中不需要的操作。的但在优先队列中不需要的操作。n二叉堆二叉堆二叉堆二叉堆(binary heap)堆的定义堆的定义二叉堆的性质:结构性质、堆序性质二叉堆的性质:结构性质、堆序性质二叉堆的操作:二叉堆的操作:insert、deleteMin、buildHeap二叉堆的应用:选择问题、事件模拟二叉堆的应用:选择问题、事件模拟堆的定义堆的定义堆
3、是满足下列性质的数列堆是满足下列性质的数列r1,r2,,rn:或或(小顶堆小顶堆)(大顶堆大顶堆)若将此序列所存储的一维数组若将此序列所存储的一维数组R1.n看做是一棵完全二看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的叉树的存储结构,则堆实质上是满足如下性质的完全二完全二叉树叉树:树中任一非叶结点的树中任一非叶结点的关键字均不大于关键字均不大于(或不小于或不小于)其左其左右孩子右孩子(若存在若存在)结点的关键字。结点的关键字。堆的定义堆的定义小顶堆:小顶堆:根结点根结点(亦称为堆顶亦称为堆顶)的关键字是堆里所有结点关键字的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。中最小者
4、的堆称为小顶堆。大顶堆:大顶堆:根结点根结点(亦称为堆顶亦称为堆顶)的关键字是堆里所有结点关键字的关键字是堆里所有结点关键字中最大者,称为大顶堆。中最大者,称为大顶堆。注意:注意:堆中任一子树亦是堆。堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆以上讨论的堆实际上是二叉堆(Binary Heap),类,类似地可定义似地可定义k叉堆。叉堆。堆的定义堆的定义(13,38,27,50,76,65,49,97)1338275076654997(96,83,27,38,11,9)小顶堆小顶堆96832738119大顶堆大顶堆二叉堆的结构性质二叉堆的结构性质n二叉堆是一棵完全二叉树。所以,二叉堆是一棵完全
5、二叉树。所以,可以用数组来表示。可以用数组来表示。ABCDEFGHIJA B C D E F G H IJ0 1 2 3 4 5 6 7 8 9 10 11 12 13n对于数组中任一位置对于数组中任一位置i上的元素,上的元素,其左孩子在位置其左孩子在位置2i上,右孩子在上,右孩子在左孩子后的位置左孩子后的位置(2i+1)上。它的上。它的父节点在父节点在 i/2 的位置上。的位置上。图中二叉堆大小的限界是图中二叉堆大小的限界是13个元素。个元素。n在一个二叉堆中,对于每一个节点在一个二叉堆中,对于每一个节点X,X的父亲中的关键字的父亲中的关键字小于(或等于)小于(或等于)X中的关键字,根节点除
6、外。中的关键字,根节点除外。二叉堆的堆序性质二叉堆的堆序性质132116631 19686526321321162431 1968652632二叉堆二叉堆非二叉堆非二叉堆根据二叉堆的堆序性质根据二叉堆的堆序性质最小元总可以在根处找到最小元总可以在根处找到n所有的操作都要保证堆序性质。所有的操作都要保证堆序性质。二叉堆的操作二叉堆的操作insert插入操作的基本思想:插入操作的基本思想:创建一个空穴,再将空穴上冒,这种创建一个空穴,再将空穴上冒,这种策略叫上滤策略叫上滤(percolate up)。二叉堆的操作二叉堆的操作insert1321162431 1968652632尝试插入尝试插入14
7、1321162431 1968652632 312114public void insert(AnyType x)if(currentSize=array.length-1)enlargeArray(array.length*2+1);int hole=+currentSize;for(;hole1&pareTo(arrayhole/2)0;hole/=2)arrayhole=arrayhole/2;arrayhole=x;二叉堆的操作二叉堆的操作insert二叉堆的操作二叉堆的操作deleteMindeleteMin(删除最小元删除最小元)操作的基本思想:操作的基本思想:即删除根节点。在根节
8、点建立一个空穴,即删除根节点。在根节点建立一个空穴,然后将堆中最后一个元素然后将堆中最后一个元素X移动到该堆的移动到该堆的某个地方后仍构成二叉堆这种策略叫下滤某个地方后仍构成二叉堆这种策略叫下滤(percolate down)或筛选或筛选二叉堆的操作二叉堆的操作deleteMin13211619196865263231211413211619196865263231211414192631public AnyType deleteMin()if(isEmpty()throw new UnderflowException();AnyType minItem=findMin();array1=ar
9、raycurrentSize-;percolateDown(1);return minItem;二叉堆的操作二叉堆的操作deleteMinprivate void percolateDown(int hole)int child;AnyType tmp=arrayhole;for(;hole*2=currentSize;hole=child)child=hole*2;if(child!=currentSize&arraychild+pareTo(arraychild)0)child+;if(pareTo(tmp)0;i-)percolateDown(i);优先队列的应用优先队列的应用选择问题选择问题输入输入N个元素及一个整数个元素及一个整数k,这,这N个元个元素的集可以是全序集。素的集可以是全序集。该选择问题是要找出第该选择问题是要找出第k个最大元素。个最大元素。当当k=N时,算法称为堆排序。时,算法称为堆排序。小结和作业小结和作业1.1.基本模型基本模型 3.3.二叉堆二叉堆2.2.实现思考实现思考 1 1堆的定义堆的定义 3 3二叉堆的操作二叉堆的操作 插入插入 删除删除 创建堆创建堆2 2堆的性质堆的性质 优先队列优先队列 作业作业:6.2、6.3
限制150内