计算机问题求解一论题2-12 堆与堆排序 2018年05月14日
计算机问题求解 – 论题2-12 - 堆与堆排序 2018年05月14日
堆性质 如果我们要定义堆 的ADT,在其数据 部分，我们应该给 出什么约束？ ·树T满足偏序树性质当且仅当树中任一结点的键值不小于 (或不大于)其子结点（如果有）的键值。 树T满足几乎完全二叉性质 口最底一层可能不满，但必须从左到右填充
堆性质 ◼ 树T 满足偏序树性质 当且仅当 树中任一结点的键值不小于 （或不大于）其子结点（如果有）的键值。 ◼ 树T满足几乎完全二叉性质 ❑ 最底一层可能不满，但必须从左到右填充 如果我们要定义堆 的ADT，在其数据 部分，我们应该给 出什么约束？
间题1： 堆与我们上次讨论的队列与 栈最突出的差别是什么？ 其特征与对象的内容相关， 一定是源于具体应用
其特征与对象的内容相关, 一定是源于具体应用
6 12345678910 1614108793241 问题2： A[PARENT(i)】≥A[] 为什么我们常用数组来实现堆？ A[PARENT(i)】≤A[叮 偏序树性质在数组实现中如何表示？ Parent(A.heapsize) <=A.heapsize/2 几乎完全性质在数组实现中如何体现？
为什么我们常用数组来实现堆？ 偏序树性质在数组实现中如何表示？ 几乎完全性质在数组实现中如何体现？ Parent(A.heapsize) <=A.heapsize/2
16 10 特别注意 (b) MAX-HEAPIFY(A.i) 下largest 1 /LEFT(i) 2 r=RIGHT(i) 3 if I A.heap-size and A[l]>A[i] 4 largest =I 5 else largest =i 6 if r A.heap-size and A[r]>A[largest] 7 largest =r 8 if largest≠i 9 exchange A[i]with A[largest] 10 MAX-HEAPIFY(A,largest) 问题4： 你能利用上图解释Max-Heapify!吗？
特别注意一 下largest
16 6 MAX-HEAPIFY(A,i) 10 0 1 I=LEFT(i) 2 r=RIGHT(i) 3 if1 A.heap-size and A[l]>Ali] 4 largest =I 5 else largest =i (b】 6 ifr A.heap-size and A[r]>A[largest] 7 largest =r 8 if largest≠i 16 9 exchange A[i]with A[largest] 10 MAX-HEAPIFY (A,largest) MAX-Heapify操作的pre/post--condition是什么？ Pre-condition:i的子女均已是某个大堆的根节点！ Post-condition:以i为根，构成一个大堆！
MAX-Heapify操作的pre/post-condition是什么？ Pre-condition: i的子女均已是某个大堆的根节点！ Post-condition: 以i为根，构成一个大堆！
Worst-case Analysis for Max-Heapify ·过程Max-Heapify中不包含循环，所以，如果不递归，其 代价是O(1)。 口如果考虑比较运算的次数，每“下沉”一层，执行2次比较。 ·递归：T(m)≤T(2n/3)+Θ(1) 问题5： 为什么2n/3? The solution to this recurrence,by case 2 of the master theorem (Theorem 4.1). is T(n)=0(lg n).Altematively,we can characterize the running time of MAX- HEAPIFY on a node of height h as ()
Worst-case Analysis for Max-Heapify ◼ 过程Max-Heapify中不包含循环，所以，如果不递归，其 代价是O(1)。 ❑ 如果考虑比较运算的次数，每“下沉”一层，执行2次比较。 ◼ 递归：
造“堆”：自底向上 413216 9 101487 ·分界线 问题6：这5个子树 LA.length/2] 己经是“堆”了？ 其实后T27个子树 10 己经是“堆”了 其实算法循环从 A.length开始又何妨？
问题6：这5个子树 已经是“堆”了？ 造“堆”：自底向上 分界线 其实后┌n/2┒个子树 已经是“堆”了 其实算法循环从 A.length开始又何妨？
A413216910487 BUILD-MAX-HEAP(A) 16 1 A.heap-size A.length 14 8 2 for i =A.length/2]downto 1 a 3 MAX-HEAPIFY(A,i) 10 16 问题6： e】 (d) 这个循环的 16 invariant是什么？ 2 (8 1 2
Built--Max-Heap正确性证明 At the start of each iteration of the for loop of lines 2-3,each node i+1. i+2.....nis the root of a max-heap. Initialization:Prior to the first iteration of the loop,i=n/2.Each node n/2+1.n/+2.....n is a leaf and is thus the root of a trivial max-heap. Maintenance:To see that each iteration maintains the loop invariant,observe that the children of node i are numbered higher than i.By the loop invariant,there- fore,they are both roots of max-heaps.This is precisely the condition required for the call MAX-HEAPIFY(A.i)to make node i a max-heap root.Moreover, the MAX-HEAPIFY call preserves the property that nodes i+1.i+2.....n are all roots of max-heaps.Decrementing i in the for loop update reestablishes the loop invariant for the next iteration. Termination:At termination,i=0.By the loop invariant,each node 1,2.....m is the root of a max-heap.In particular,node 1 is
Built-Max-Heap正确性证明