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

优先级队列、堆排序2016Fall《数据结构》2022/12/191优先级队列

PriorityQueue2022/12/19与栈和队列一样：可以保存数据元素，访问、入、出不同之处：每个数据都附有优先级，任何时候访问、出对列的总是当前队列中最优先的元素“有序”队列！2022/12/19优先级队列classPrioQue: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：sortedlist2022/12/19

defdequeue(self):ifself.is_empty():raisePrioQueueError("inpop")returnself.elems.pop()

#元素由大到小排，直接pop

defenqueue(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)2022/12/19

入队列时保持有序，出队列直接pop；入队列：O(n)出对列：O(1)入队列时不处理，出队列时搜索最优先：入队列：O(1)出队列：O(n)线性方式两种策略2022/12/19堆结构

Heap2022/12/19堆顶的“优先级”最高

【数最小~~小顶堆】上面轻，下面沉；上面气泡，下面石头气泡上浮，石头下沉“土堆”2022/12/19堆（递归定义）空树；若非空，是一棵完全二叉树，满足：若根结点有左孩子，则根结点值小于等于其左孩子值；若根结点有右孩子，则根结点值小于等于其右孩子值；左右子树仍然是堆！堆的表示2022/12/19适合顺序存储结点i的孩子：2*i+1，2*i+2结点i的双亲：(i-1)/2由根到叶子的路径长~logn含有n个结点的完全二叉树的深度：log2n

回忆：完全二叉树的性质2022/12/19堆的表示顺序存储！！！

012345671236248547305391含n个元素的线性序列elem[0,…n-1]，满足：elem[i]<=elem[2*i+1]，如果2*i+1<nelem[i]<=elem[2*i+2]，如果2*i+2<n堆的另一种定义2022/12/19012345671236248547305391存储上：线性结构逻辑上：完全二叉树（层次结构）对堆结构的理解2022/12/19如何向堆中插入元素？？？2022/12/1901234567123624854730539125尾部插入元素后的siftup123624304785539125123624304725539185122524304736539185

defsiftup(self,e,last):#i上行范围[last,0)elems=self.elemsi,j=last,(last-1)//2#j是i的双亲

whilei>0ande<elems[j]:elems[i]=elems[j]#把双亲挤下来——对应小数上浮i,j=j,(j-1)//2#继续上行

elems[i]=e

时间复杂度：O(logn)siftup——向上筛选2022/12/19如何由堆中删除元素？？？2022/12/19012345671338274976654997输出堆顶后的siftdown过程左右两棵子树已经是堆，将最后一个元素充填堆顶，让其根据“重量”自然下沉：效果是把小的孩子向上挤！siftdown——从根开始沿小孩子下行2022/12/19j是i的小孩子

iii的小孩子j

defsiftdown(self,e,begin,end):#j的下行范围<end

elems=self.elems,i,j=begin,begin*2+1whilej<end:ifj+1<endandelems[j+1]<elems[j]:j+=1#选出小孩子

ife<elems[j]:breakelems[i]=elems[j]#孩子挤上去——对应大数下沉i,j=j,2*j+1#继续下行elems[i]=e

时间复杂度：O(logn)siftdown——向下筛选2022/12/19如何建堆？？？2022/12/194938651376972749012345674938659776132749明确：

最先一个没有孩子的结点的编号为：(n-1-1)/2+1=n/2

从n/2开始的每个结点没有孩子，各自成一个堆

如何建堆？？？2022/12/194938651376972749n=8index(76)=4起始：对于最后一个有孩子的结点，它的左右子树都已经是堆；自后向前，逐结点进行siftdown操作，将子堆不断合成更大些的堆，最终形成一个大堆。建堆过程2022/12/19建堆过程从最后一个有孩子的结点开始，逐个siftdown

defbuildheap(self):end=len(self.elems)foriinrange(end//2-1,-1,-1):self.siftdown(self.elems[i],i,end)

#siftdown操作范围：[i,end)

建堆2022/12/19建堆的时间复杂度2022/12/19建堆时，从倒数第二层的加点开始，自后向前，逐步进行siftdown；siftdown过程中，每一步做两次比较；两个孩子选出最小的sift的结点和小的孩子结点比较

第i层向下sift的层数最多为h-i第i层最多2i个结点总的比较次数为：时间复杂度：O(n)建堆的时间复杂度2022/12/19优先级队列的堆实现2022/12/19classPrioQueue: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：堆2022/12/19defenqueue(self,e):self.elems.append(None)#添加占位self.siftup(e,len(self.elems)-1)#last

defdequeue(self):ifself.is_empty():raisePrioQueueError("inpop")elems=self.elems

e0=elems[0]e=elems.pop()#弹出最后一个，“占位”elem[0]iflen(elems)>0:self.siftdown(e,0,len(elems))#[0,len)returne02022/12/19

初始一次性建堆：O(n)出队列：O(logn)入队列：O(logn)堆方式2022/12/19堆排序

HeapSort2022/12/19step1：对序列建堆；step2：不断输出堆顶元素，然后通过siftdown再次调整成元素数少1的堆，直到所有元素输出。堆结构的应用——堆排序2022/12/19堆排序2022/12/19小顶堆排序的结果是由大到小！堆排序defheap_sort(elems):defsiftdown(elems,e,begin,end):#[begin,end)i,j=begin,begin*2+1whilej<end:ifj+1<endandelems[j+1]<elems[j]:j+=1ife<elems[j]:breakelems[i]=elems[j]i,j=j,2*j+1elems[i]=e

end=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)