数据结构与算法(Python语言描述)课件DS_053_优先级队列和堆排序

优先级队列、堆排序2016Fall《数据结构》2020/3/291中国海洋大学数学科学学院优先级队列PriorityQueue2020/3/29与栈和队列一样：可以保存数据元素，访问、入、出不同之处：每个数据都附有优先级，任何时候访问、出对列的总是当前队列中最优先的元素“有序”队列！2020/3/29优先级队列代表了数据的某种性质：各项工作的计划开始时间一个大项目中各种工作任务的急迫程度银行客户的诚信评估，用于决定优先贷款等优先级（Priority）2020/3/29classPrioQue:def__init__(self,elist=[]):self.elems=list(elist)self.elems.sort(reverse=True)#由大到小排序defis_empty(self):returnself.elems==[]defpeek(self):ifself.is_empty():raisePrioQueueError(intop)returnself.elems[-1]实现方式1：sortedlist2020/3/29defdequeue(self):ifself.is_empty():raisePrioQueueError(inpop)returnself.elems.pop()#元素由大到小排，直接popdefenqueue(self,e):i=len(self.elems)-1whilei=0:ifself.elems[i]=e:i-=1else:breakself.elems.insert(i+1,e)#循环结束时，遇到了第一个大于e的元素elems[i]#入队列的时间复杂度：O(n)2020/3/29入队列时保持有序，出队列直接pop；入队列：O(n)出对列：O(1)入队列时不处理，出队列时搜索最优先：入队列：O(1)出队列：O(n)线性方式两种策略2020/3/29堆结构Heap2020/3/29大顶堆和小顶堆堆顶的“优先级”最高【数最小~~小顶堆】上面轻，下面沉；上面气泡，下面石头气泡上浮，石头下沉“土堆”2020/3/29堆是一棵“基本有序”的完全二叉树！任何结点的值都小于等于其左右孩子的值！堆（递归定义）空树；若非空，是一棵完全二叉树，满足：•若根结点有左孩子，则根结点值小于等于其左孩子值；•若根结点有右孩子，则根结点值小于等于其右孩子值；•左右子树仍然是堆！特点：最优先的元素位于堆顶；左右子树仍然是堆；由根到叶子的路径上，结点是有序的；应用：表示优先级队列！堆排序堆2020/3/29堆的表示2020/3/29适合顺序存储结点i的孩子：2*i+1，2*i+2结点i的双亲：(i-1)/2由根到叶子的路径长~logn含有n个结点的完全二叉树的深度：log2n回忆：完全二叉树的性质2020/3/29堆的表示顺序存储！！！012345671236248547305391含n个元素的线性序列elem[0,…n-1]，满足：elem[i]=elem[2*i+1]，如果2*i+1nelem[i]=elem[2*i+2]，如果2*i+2n堆的另一种定义2020/3/29012345671236248547305391存储上：线性结构逻辑上：完全二叉树（层次结构）对堆结构的理解2020/3/29堆的维护——插入删除2020/3/29如何向堆中插入元素？？？2020/3/2901234567123624854730539125尾部插入元素后的siftup123624304785539125123624304725539185122524304736539185siftup——从尾部开始沿双亲上行2020/3/29j=(last-1)/2i=lasti=jj=(j-1)/2defsiftup(self,e,last):#i上行范围[last,0)elems=self.elemsi,j=last,(last-1)//2#j是i的双亲whilei0andeelems[j]:elems[i]=elems[j]#把双亲挤下来——对应小数上浮i,j=j,(j-1)//2#继续上行elems[i]=e时间复杂度：O(logn)siftup——向上筛选2020/3/29如何由堆中删除元素？？？2020/3/29012345671338274976654997输出堆顶后的siftdown过程133827657649499738276576494997973827657649492738976576494927384965764997输出堆顶后的siftdown过程左右两棵子树已经是堆，将最后一个元素充填堆顶，让其根据“重量”自然下沉：效果是把小的孩子向上挤！siftdown——从根开始沿小孩子下行2020/3/29j是i的小孩子iii的小孩子jdefsiftdown(self,e,begin,end):#j的下行范围endelems=self.elems,i,j=begin,begin*2+1whilejend:ifj+1endandelems[j+1]elems[j]:j+=1#选出小孩子ifeelems[j]:breakelems[i]=elems[j]#孩子挤上去——对应大数下沉i,j=j,2*j+1#继续下行elems[i]=e时间复杂度：O(logn)siftdown——向下筛选2020/3/29建堆2020/3/29如何建堆？？？2020/3/294938651376972749012345674938659776132749明确：最先一个没有孩子的结点的编号为：•(n-1-1)/2+1=n/2从n/2开始的每个结点没有孩子，各自成一个堆如何建堆？？？2020/3/294938651376972749n=8index(76)=4起始：对于最后一个有孩子的结点，它的左右子树都已经是堆；自后向前，逐结点进行siftdown操作，将子堆不断合成更大些的堆，最终形成一个大堆。建堆过程2020/3/29建堆过程从最后一个有孩子的结点开始，逐个siftdowndefbuildheap(self):end=len(self.elems)foriinrange(end//2-1,-1,-1):self.siftdown(self.elems[i],i,end)#siftdown操作范围：[i,end)建堆2020/3/29建堆的时间复杂度2020/3/29建堆时，从倒数第二层的加点开始，自后向前，逐步进行siftdown；siftdown过程中，每一步做两次比较；两个孩子选出最小的sift的结点和小的孩子结点比较第i层向下sift的层数最多为h-i第i层最多2i个结点总的比较次数为：时间复杂度：O(n)建堆的时间复杂度2020/3/29优先级队列的堆实现2020/3/29classPrioQueue:def__init__(self,elist=[]):self.elems=list(elist)ifelist!=[]:self.buildheap()defis_empty(self):returnlen(self.elems)==0defpeek(self):ifself.is_empty():raisePrioQueueError(intop)returnself.elems[0]实现方式2：堆2020/3/29defenqueue(self,e):self.elems.append(None)#添加占位self.siftup(e,len(self.elems)-1)#lastdefdequeue(self):ifself.is_empty():raisePrioQueueError(inpop)elems=self.elemse0=elems[0]e=elems.pop()#弹出最后一个，“占位”elem[0]iflen(elems)0:self.siftdown(e,0,len(elems))#[0,len)returne02020/3/29初始一次性建堆：O(n)出队列：O(logn)入队列：O(logn)堆方式2020/3/29堆排序HeapSort2020/3/29step1：对序列建堆；step2：不断输出堆顶元素，然后通过siftdown再次调整成元素数少1的堆，直到所有元素输出。堆结构的应用——堆排序2020/3/29堆排序2020/3/29小顶堆排序的结果是由大到小！堆排序defheap_sort(elems):defsiftdown(elems,e,begin,end):#[begin,end)i,j=begin,begin*2+1whilejend:ifj+1endandelems[j+1]elems[j]:j+=1ifeelems[j]:breakelems[i]=elems[j]i,j=j,2*j+1elems[i]=eend=len(elems)foriinrange(end//2-1,-1,-1):#初始建堆siftdown(elems,elems[i],i,end)foriinrange((end-1),0,-1):#不断输出堆顶，然后调整e=elems[i]elems[i]=elems[0]#堆顶输出后，放到当前的最后siftdown(elems,e,0,i)#注意：堆的范围在缩小时间：O(nlogn)建堆：O(n)不断输出堆顶、调整：O(nlogn)•共n个元素•每个元素输出后的siftdown，不超过树的深度•log(n-1)+…+log(2)nlogn空间：O(1)堆排序的复杂度分析2020/3/29小结2020/3/29堆结构的特点逻辑上是“基本有序”的完全二叉树，小顶堆堆顶最小！堆调整Siftup——小数上浮，将大的双亲挤下来；Siftdown——大数下沉，将小孩子挤上去；建堆过程：自后向前不断siftdown，逐步合成一个大堆O(n)堆排序方法：不断输出堆顶，回填后再siftdownO(nlogn)要求掌握！2020/3/29