数据结构堆与优先队列.ppt

*/84 * 最大堆的初始化 根据int a[10]={20,12,35,15,10,80,30,17,2,1}建立最大堆 20 12 35 15 10 80 30 17 2 1 0 1 2 3 4 5 6 7 8 9 * 最大堆的初始化step1 已知n=10; i=(n-1)/2=4; 20 12 35 15 10 80 30 17 2 1 0 1 2 3 4 5 6 7 8 9 i 20 12 35 15 10 80 30 17 2 1 0 1 2 3 4 5 6 7 8 9 * 最大堆的初始化step2 i=3 20 12 35 15 10 80 30 17 2 1 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 i 2i+1 2i+2 * 最大堆的初始化step3 i=2 20 12 35 17 10 80 30 15 2 1 0 1 2 3 4 5 6 7 8 9 20 12 35 17 10 80 30 15 2 1 0 1 2 3 4 5 6 7 8 9 i 2i+1 2i+2 * 最大堆的初始化step4_0 i=1 20 12 80 17 10 35 30 15 2 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 i 2i+1 2i+2 * 最大堆的初始化step4_1 i=1,j=2i+1=3 20 17 80 12 10 35 30 15 2 1 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 j 2j+1 2j+2 * 最大堆的初始化step5_0 i=0 20 17 80 15 10 35 30 12 2 1 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 i 2i+1 2i+2 * 最大堆的初始化step5_1 i=0,j=2i+2=2 80 17 20 15 10 35 30 12 2 1 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 j 2j+1 2j+2 * 最大堆的初始化step5_2 80 17 35 15 10 20 30 12 2 1 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 */84 * 最大堆的删除1 21 15 14 10 20 2 最大堆的删除：删除堆的根部元素 删除21, 得到的堆结构： 15 14 10 20 2 2 15 14 10 20 20 15 14 10 2 * 最大堆的删除2 最大堆的删除：删除堆的根部元素 删除20, 得到的堆结构： 15 14 2 10 10 15 14 2 20 15 14 10 2 15 14 2 10 15 14 10 2 */84 例，序列 49 38 65 97 76 13 27 50 1. 按顺序依次构造成完全二叉树的结点； 49 38 65 97 76 13 27 50 2. 把完全二叉树改造成堆； 从下向上，父子交换； 50 97 13 65 13 49 49 27 3. 取得最小值 13 4. 删除 13 ，重新改造成新堆； 13 97 27 97 97 49 5. 取得次小值 27； 6. 删除 27 ，重新改造成新堆； 97 27 97 38 97 50 7. 取得次次小值 38； 堆排序 */84 课堂练习 关键码序列K = {12，14，15，19，20，17，18，24，22，26}所对应的最小堆 */84 建堆效率 对于n个结点的堆，其对应的完全二叉树的层数为logn。 设i表示二叉树的层编号，则第i层上的结点数最多为2i(i ≥ 0)。 建堆的过程中，对每一个非叶子结点都调用了一次SiftDown调整算法，而每个数据元素最多向下调整到最底层，即第i层上的结点向下调整到最底层的调整次数为logn – i。因此，建堆的计算时间为 （公式5.3） 令j = logn –