《堆与优先队列课件》由会员分享，可在线阅读，更多相关《堆与优先队列课件（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构、算法及应用数据结构、算法及应用3.2 3.2 二叉树二叉树堆与优先队列堆与优先队列堆与优先队列堆与优先队列堆定义堆初始化堆插入堆删除（删除堆顶元素）优先队列主要内容主要内容复习完全二叉树：定义？性质？存储？完全二叉树：定义？性质？存储？202012123535151510108080303017172 21 10 01 12 23 34 45 56 67 78 89 9202012123535151510108080303017172 21 10 01 12 23 34 45 56 67 78 89 9堆定义最大树最大树（最小树最小树）:每个结点的值都每个结点的值都大于大于（小于小于
2、）或等于其子结点（如果有的话）值的树。或等于其子结点（如果有的话）值的树。最大堆最大堆（最小堆最小堆）：）：最大最大（最小最小）的完全二叉树。）的完全二叉树。堆定义1414121210108 87 76 69 96 65 5303025252 27 710108 84 46 610102020505011112121最大树最大树最小树最小树堆的操作插入插入初始化初始化删除删除最大堆的插入120201515141410102 21 120201515141410102 21 1最大堆的插入220201515141410102 25 520201515141410102 22 22 22 25 5
3、20201515141410105 52 2最大堆的插入320201515141410102 2212120201515141410102 22 22 22 22 21 115151414101020202 22020202020202121212115151414101020202 2最大堆的初始化建立建立n个元素的堆：个元素的堆：通过在初始化为空的堆中执行通过在初始化为空的堆中执行n次插次插入操作来构建堆入操作来构建堆.O(nlogn);利用不同的策率在利用不同的策率在O(n)时间内完成。时间内完成。最大堆的初始化根据根据int a10=20,12,35,15,10,80,30,17,2,
4、1int a10=20,12,35,15,10,80,30,17,2,1建立最大建立最大堆堆202012123535151510108080303017172 21 10 0 0 01 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 89 9 9 912最大堆的初始化step1已知已知n=10;i=(n-1)/2=4;n=10;i=(n-1)/2=4;202012123535151510108080303017172 21 10 01 12 23 34 45 56 67 78 89 9i i20201212353515151010808
5、0303017172 21 10 01 12 23 34 45 56 67 78 89 913最大堆的初始化step2i=3i=3202012123535151510108080303017172 21 10 01 12 23 34 45 56 67 78 89 9202012123535151510108080303017172 21 10 01 12 23 34 45 56 67 78 89 9i i2i+12i+12i+22i+2最大堆的初始化step3i=2i=2202012123535171710108080303015152 21 10 01 12 23 34 45 56 67 7
6、8 89 9202012123535171710108080303015152 21 10 01 12 23 34 45 56 67 78 89 9i i2i+12i+12i+22i+2最大堆的初始化step4_0i=1i=1202012128080171710103535303015152 21 10 01 12 23 34 45 56 67 78 89 9202012128080171710103535303015152 21 10 01 12 23 34 45 56 67 78 89 9i i2i+12i+12i+22i+2最大堆的初始化step4_1i=1,j=2i+1=3i=1,j=
7、2i+1=3202017178080121210103535303015152 21 10 01 12 23 34 45 56 67 78 89 9202017178080121210103535303015152 21 10 01 12 23 34 45 56 67 78 89 9j j2j+12j+12j+22j+2最大堆的初始化step5_0i=0i=0202017178080151510103535303012122 21 10 01 12 23 34 45 56 67 78 89 9202017178080151510103535303012122 21 10 01 12 23 34
8、 45 56 67 78 89 9i i2i+12i+12i+22i+218最大堆的初始化step5_1i=0,j=2i+2=2i=0,j=2i+2=2808017172020151510103535303012122 21 10 01 12 23 34 45 56 67 78 89 9808017172020151510103535303012122 21 10 01 12 23 34 45 56 67 78 89 9j j2j+12j+12j+22j+219最大堆的初始化step5_2808017173535151510102020303012122 21 10 01 12 23 34 4
9、5 56 67 78 89 9808017173535151510102020303012122 21 10 01 12 23 34 45 56 67 78 89 9最大堆的删除1212115151414101020202 2最大堆的删除：删除堆的根部元素最大堆的删除：删除堆的根部元素删除删除21,21,得到得到的堆结构：的堆结构：15151414101020202 22 2151514141010202020201515141410102 221最大堆的删除2最大堆的删除：删除堆的根部元素最大堆的删除：删除堆的根部元素删除删除20,20,得到得到的堆结构：的堆结构：151514142 210
10、101010151514142 220201515141410102 2151514142 210101515141410102 2堆排序例，序列例，序列 49 38 65 97 76 13 27 501.按顺序依次构造成完全二叉树的结点；按顺序依次构造成完全二叉树的结点；49386597761327502.把完全二叉树改造成把完全二叉树改造成堆堆；从下向上，父子交换；从下向上，父子交换；50971365134949273.取得最小值取得最小值 134.删除删除 13，重新改造成新堆；，重新改造成新堆；1397279797495.取得次小值取得次小值 27；6.删除删除 27，重新改造成新堆；
11、，重新改造成新堆；9727973897507.取得次次小值取得次次小值 38；课堂练习课堂练习关键码序列K=12，14，15，19，20，17，18，24，22，26所对应的最小堆建堆效率建堆效率对于对于n个结点的堆，其对应的完全二叉树的层数为个结点的堆，其对应的完全二叉树的层数为logn。设设i表示二叉树的层编号，则第表示二叉树的层编号，则第i层上的结点数最多为层上的结点数最多为2i(i 0)。建堆的过程中，对每一个非叶子结点都调用了一次建堆的过程中，对每一个非叶子结点都调用了一次SiftDown调调整算法，而每个数据元素最多向下调整到最底层，即第整算法，而每个数据元素最多向下调整到最底层，
12、即第i层上的结层上的结点向下调整到最底层的调整次数为点向下调整到最底层的调整次数为logn i。因此，。因此，建堆的计算时建堆的计算时间间为为 令令j=logn i，则则 建堆效率建堆效率建堆算法的时间复杂度是O(n)。这就说明可以在线性时间内把一个无序的序列转化成堆序由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和最差时间代价都是(log n)最小堆只适合于查找最小值，查找任意值的效率不高优先队列优先队列优先队列(priority queue)是一种有用的数据结构。它是0个或多个元素的集合，每个元素都有一个关键码值，执行的操作有查找、插入和删除一个元素。优先队列的主要特点是支持从一个集合中快速地查找并移出具有最大值或最小值的元素。最小优先队列，适合查找和删除最小元素；最大优先队列中，适合查找和删除最大元素。堆是一种很好的优先队列实现方法作业纸面作业：纸面作业：P142：12,13上机作业：上机作业：定义堆，封装初始化、插入、删除堆顶元素定义堆，封装初始化、插入、删除堆顶元素的操作的操作
