计算机问题求解一论题2-12 堆与堆排序 2016年05月05日
计算机问题求解 – 论题2-12 - 堆与堆排序 2016年05月05日
16 10 12345678910 1614108793241 问题1： 为什么有时可以将数组理解为二叉树？ 为什么数组会有一个A.heap-size?
间题2： 堆与我们上次讨论的队列与 栈最突出的差别是什么？ 其特征与对象的内容相关， 一定是源于具体应用
其特征与对象的内容相关, 一定是源于具体应用
堆（偏序树）性质 ·树T满足偏序树性质当且仅当树中任一结点的键值不小于 (或不大于)其子结点（如果有）的键值。 ·此性质在数组实现中的表示： Max-heap: A[PARENTO(i)】≥A[] oMin-heap: APARENT(i)】≤A[] 如果我们要定义堆的 ADT,在其数据部分， 我们应该给出什么约束？
堆（偏序树）性质 树T 满足偏序树性质 当且仅当 树中任一结点的键值不小于 （或不大于）其子结点（如果有）的键值。 此性质在数组实现中的表示： Max-heap: Min-heap: 如果我们要定义堆的 ADT，在其数据部分， 我们应该给出什么约束？
问题3： Max-Heapify的 precondition 是什么？ b 特别解释一下 MAX-HEAPIFY(A,i) largest 16 11 LEFT(i) 2 r=RIGHT(i) 3ifl≤A.heap-size and A[W￥A[i] 4 largest =I 5 else largest =i (c) 6 if r A.heap-size and A[rl>A[largest] 7 largest =r 8 if largest≠i 问题4： 9 exchange A[i]with Allargest] 10 MAX-HEAPIFY (A,largest) 你能利用上图解释Max-Heapifyl吗？
特别解释一下 largest 问题3： Max-Heapify的 precondition 是什么？