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

* 算法：从第一个具有孩子的结点i开始（i=[n/2]），如果以这个元素为根的子树已是最大堆，则不需调整，否则需调整子树使之成为堆。继续检查i-1，i-2等结点为根的子树，直到检查整个二叉树的根结点(其位置为１)。 数据结构、算法及应用 3.2 二叉树 堆与优先队列 堆定义 堆初始化 堆插入 堆删除（删除堆顶元素） 优先队列 主要内容 复习 完全二叉树：定义？性质？存储？ 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 堆定义 最大树（最小树）:每个结点的值都大于（小于）或等于其子结点（如果有的话）值的树。 最大堆（最小堆）：最大（最小）的完全二叉树。 堆定义 14 12 10 8 7 6 9 6 5 30 25 2 7 10 8 4 6 10 20 50 11 21 最大树 最小树 堆的操作 插入 初始化 删除 最大堆的插入1 20 15 14 10 2 1 20 15 14 10 2 1 最大堆的插入2 20 15 14 10 2 5 20 15 14 10 2 2 2 2 5 20 15 14 10 5 2 最大堆的插入3 20 15 14 10 2 21 20 15 14 10 2 2 2 2 21 15 14 10 20 2 20 20 20 21 21 15 14 10 20 2 最大堆的初始化 建立n个元素的堆： 通过在初始化为空的堆中执行n次插入操作来构建堆.O(nlogn); 利用不同的策率在O(n)时间内完成。 最大堆的初始化 根据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 最大堆的删除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 1