数据结构与算法Python语言描述DS优先级队列和堆排序学习教案.pptx

会计学优先级队列(duìliè)PriorityQueue与栈和队列(duìliè)一样：
可以保存数据元素，访问、入、出

不同之处：每个数据都附有优先级，任何时候访问、出对列的总是当前队列(duìliè)中最优先的元素
“有序”队列(duìliè)！代表了数据(shùjù)的某种性质：
各项工作的计划开始时间
一个大项目中各种工作任务的急迫程度
银行客户的诚信评估，用于决定优先贷款等classPrioQue:
def__init__(self,elist=[]):
self.elems=list(elist)
#由大到小排序(páixù)

defis_empty(self):
returnself.elems==[]

defpeek(self):
ifself.is_empty():
raisePrioQueueError("intop")
returnself.elems[-1] defdequeue(self):
ifself.is_empty():
raisePrioQueueError("inpop")

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

defenqueue(self,e):
i=len(self.elems)-1
whilei>=0:
ifself.elems[i]<=e:
i-=1
else:
break
i+1,e)
#循环结束时，遇到了第一个大于e的元素elems[i]

#入队列(duìliè)的时间复杂度：O(n)入队列时保持有序，出队列直接pop；
入队列：O(n)
出对列：O(1)
入队列时不处理(chǔlǐ)，出队列时搜索最优先：
入队列：O(1)
出队列：O(n)堆结构(jiégòu)Heap大顶堆和小顶堆堆顶的“优先级”最高【数最小~~小顶堆】
上面轻，下面沉；上面气泡，下面石头(shítou)
气泡上浮，石头(shítou)下沉堆堆（递归定义(dìngyì)）特点：
最优先的元素位于堆顶；
左右(zuǒyòu)子树仍然是堆；
由根到叶子的路径上，结点是有序的；

应用：
表示优先级队列！
堆排序堆的表示(biǎoshì)适合顺序存储
结点(jiédiǎn)i的孩子：2*i+1，2*i+2
结点(jiédiǎn)i的双亲：(i-1)/2

由根到叶子的路径长~logn
含有n个结点(jiédiǎn)的完全二叉树的深度：log2n
堆的表示(biǎoshì)含n个元素的线性序列(xùliè)elem[0,…n-1]，满足：
elem[i]<=elem[2*i+1]，如果2*i+1<n
elem[i]<=elem[2*i+2]，如果2*i+2<n存储上：线性结构(jiégòu)
逻辑上：完全二叉树（层次结构(jiégòu)）堆的维护(wéihù)——插入删除如何向堆中插入(chārù)元素？？？尾部插入(chārù)元素后的siftupsiftup——从尾部开始(kāishǐ)沿双亲上行defsiftup(self,e,last):#i上行范围[last,0)
elems=self.elems
i,j=last,(last-1)//2#j是i的双亲

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

elems[i]=e

时间复杂度：O(logn)如何(rúhé)由堆中删除元素？？？输出(shūchū)堆顶后的siftdown过程输出(shūchū)堆顶后的siftdown过程siftdown——从根开始(kāishǐ)沿小孩子下行defsiftdown(self,e,begin,end):#j的下行(xiàxíng)范围<end
elems=self.elems,
i,j=begin,begin*2+1

whilej<end:
ifj+1<endandelems[j+1]<elems[j]:
j+=1#选出小孩子

ife<elems[j]:
break

elems[i]=elems[j]#孩子挤上去——对应大数下沉
i,j=j,2*j+1#继续下行(xiàxíng)

elems[i]=e

时间复杂度：O(logn)

建堆如何(rúhé)建堆？？？明确：
最先一个(yīɡè)没有孩子的结点的编号为：
(n-1-1)/2+1=n/2
从n/2开始的每个结点没有孩子，各自成一个(yīɡè)堆
起始：对于最后一个有孩子的结点，它的左右子树都已经是堆；
自后向前，逐结点进行siftdown操作，将子堆不断合成更大些的堆，最终(zuìzhōnɡ)形成一个大堆。建堆过程(guòchéng) defbuildheap(self)