chapter3.2_part4堆与优先队列.ppt

《chapter3.2_part4堆与优先队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.2二叉树堆与优先队列堆定义堆初始化堆插入堆删除（删除堆顶元素）优先队列主要内容复习完全二叉树：定义？性质？存储？20123515108030172101234567892012351510803017210123456789堆定义最大树（最小树）:每个结点的值都大于（小于）或等于其子结点（如果有的话）值的树。最大堆（最小堆）：最大（最小）的完全二叉树。堆定义141210876965302527108461020501121最大树最小树堆的操作插入初始化删除最大堆的插入1201514102120151

2、41021最大堆的插入2201514102520151410222252015141052最大堆的插入320151410221201514102222211514102022020202121151410202最大堆的初始化建立n个元素的堆：通过在初始化为空的堆中执行n次插入操作来构建堆.O(nlogn);利用不同的策率在O(n)时间内完成。最大堆的初始化根据inta[10]={20,12,35,15,10,80,30,17,2,1}建立最大堆201235151080301721012345678912

3、最大堆的初始化step1已知n=10;i=(n-1)/2=4;2012351510803017210123456789i201235151080301721012345678913最大堆的初始化step2i=320123515108030172101234567892012351510803017210123456789i2i+12i+2最大堆的初始化step3i=220123517108030152101234567892012351710803015210123456789i2i+12i+2最大堆的

4、初始化step4_0i=120128017103530152101234567892012801710353015210123456789i2i+12i+2最大堆的初始化step4_1i=1,j=2i+1=320178012103530152101234567892017801210353015210123456789j2j+12j+2最大堆的初始化step5_0i=020178015103530122101234567892017801510353012210123456789i2i+12i+218最

5、大堆的初始化step5_1i=0,j=2i+2=280172015103530122101234567898017201510353012210123456789j2j+12j+219最大堆的初始化step5_280173515102030122101234567898017351510203012210123456789最大堆的删除121151410202最大堆的删除：删除堆的根部元素删除21,得到的堆结构：15141020221514102020151410221最大堆的删除2最大堆的删除：删除堆的

6、根部元素删除20,得到的堆结构：1514210101514220151410215142101514102堆排序例，序列49386597761327501.按顺序依次构造成完全二叉树的结点；49386597761327502.把完全二叉树改造成堆；从下向上，父子交换；50971365134949273.取得最小值134.删除13，重新改造成新堆；1397279797495.取得次小值27；6.删除27，重新改造成新堆；9727973897507.取得次次小值38；课堂练习关键码序列K={12，14，15

7、，19，20，17，18，24，22，26}所对应的最小堆建堆效率对于n个结点的堆，其对应的完全二叉树的层数为logn。设i表示二叉树的层编号，则第i层上的结点数最多为2i(i≥0)。建堆的过程中，对每一个非叶子结点都调用了一次SiftDown调整算法，而每个数据元素最多向下调整到最底层，即第i层上的结点向下调整到最底层的调整次数为logn–i。因此，建堆的计算时间为令j=logn–i，则建堆效率建堆算法的时间复杂度是O(n)。这就说明可以在线性时间内把一个无序的序列转化成堆序由于堆有logn层深，插入

8、结点、删除普通元素和删除最小元素的平均时间代价和最差时间代价都是(logn)最小堆只适合于查找最小值，查找任意值的效率不高优先队列优先队列(priorityqueue)是一种有用的数据结构。它是0个或多个元素的集合，每个元素都有一个关键码值，执行的操作有查找、插入和删除一个元素。优先队列的主要特点是支持从一个集合中快速地查找并移出具有最大值或最小值的元素。最小优先队列，适合查找和删除最小元素；最大优先队列中，适合查找和删除最大元素。堆是一