《chapter3.2_part4堆与优先队列概要》由会员分享，可在线阅读，更多相关《chapter3.2_part4堆与优先队列概要（26页珍藏版）》请在金锄头文库上搜索。
1、3.2 二叉树,堆与优先队列,堆定义 堆初始化 堆插入 堆删除（删除堆顶元素） 优先队列,主要内容,复习,完全二叉树：定义？性质？存储？,堆定义,最大树（最小树）:每个结点的值都大于（小于）或等于其子结点（如果有的话）值的树。 最大堆（最小堆）：最大（最小）的完全二叉树。,堆定义,最大树,最小树,堆的操作,插入 初始化 删除,最大堆的插入1,最大堆的插入2,2,2,2,最大堆的插入3,2,2,2,20,20,20,最大堆的初始化,建立n个元素的堆： 通过在初始化为空的堆中执行n次插入操作来构建堆.O(nlogn); 利用不同的策率在O(n)时间内完成。,最大堆的初始化,根据int a10=20
2、,12,35,15,10,80,30,17,2,1建立最大堆,0,1,2,3,4,5,6,7,8,9,12,最大堆的初始化step1,已知n=10; i=(n-1)/2=4;,0,1,2,3,4,5,6,7,8,9,20,12,35,15,10,80,30,17,2,1,0 1 2 3 4 5 6 7 8 9,13,最大堆的初始化step2,i=3,0,1,2,3,4,5,6,7,8,9,20,12,35,15,10,80,30,17,2,1,0 1 2 3 4 5 6 7 8 9,最大堆的初始化step3,i=2,0,1,2,3,4,5,6,7,8,9,20,12,35,17,10,80,3
3、0,15,2,1,0 1 2 3 4 5 6 7 8 9,最大堆的初始化step4_0,i=1,0,1,2,3,4,5,6,7,8,9,20,12,80,17,10,35,30,15,2,1,0 1 2 3 4 5 6 7 8 9,最大堆的初始化step4_1,i=1,j=2i+1=3,0,1,2,3,4,5,6,7,8,9,20,17,80,12,10,35,30,15,2,1,0 1 2 3 4 5 6 7 8 9,最大堆的初始化step5_0,i=0,0,1,2,3,4,5,6,7,8,9,20,17,80,15,10,35,30,12,2,1,0 1 2 3 4 5 6 7 8 9,1
4、8,最大堆的初始化step5_1,i=0,j=2i+2=2,0,1,2,3,4,5,6,7,8,9,80,17,20,15,10,35,30,12,2,1,0 1 2 3 4 5 6 7 8 9,19,最大堆的初始化step5_2,0,1,2,3,4,5,6,7,8,9,80,17,35,15,10,20,30,12,2,1,0 1 2 3 4 5 6 7 8 9,最大堆的删除1,最大堆的删除：删除堆的根部元素,2,21,最大堆的删除2,最大堆的删除：删除堆的根部元素,10,堆排序,例，序列 49 38 65 97 76 13 27 50,1. 按顺序依次构造成完全二叉树的结点；,2. 把完全
5、二叉树改造成堆；,从下向上，父子交换；,3. 取得最小值 13,4. 删除 13 ，重新改造成新堆；,5. 取得次小值 27；,6. 删除 27 ，重新改造成新堆；,7. 取得次次小值 38；,课堂练习,关键码序列K = 12，14，15，19，20，17，18，24，22，26所对应的最小堆,建堆效率,对于n个结点的堆，其对应的完全二叉树的层数为logn。 设i表示二叉树的层编号，则第i层上的结点数最多为2i(i 0)。 建堆的过程中，对每一个非叶子结点都调用了一次SiftDown调整算法，而每个数据元素最多向下调整到最底层，即第i层上的结点向下调整到最底层的调整次数为logn i。因此，建
6、堆的计算时间为 令j = logn i，则,建堆效率,建堆算法的时间复杂度是O(n)。这就说明可以在线性时间内把一个无序的序列转化成堆序 由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和最差时间代价都是(log n) 最小堆只适合于查找最小值，查找任意值的效率不高,优先队列,优先队列(priority queue)是一种有用的数据结构。它是0个或多个元素的集合，每个元素都有一个关键码值，执行的操作有查找、插入和删除一个元素。 优先队列的主要特点是支持从一个集合中快速地查找并移出具有最大值或最小值的元素。最小优先队列，适合查找和删除最小元素；最大优先队列中，适合查找和删除最大元素。 堆是一种很好的优先队列实现方法,
