计算机问题求解 – 论题2-12 - 堆与堆排序 2018年05月14日 数据的组织（逻辑的，物理的）均可以影响到算法的设计和性能.

Presentation on theme: "计算机问题求解 – 论题2-12 - 堆与堆排序 2018年05月14日 数据的组织（逻辑的，物理的）均可以影响到算法的设计和性能."— Presentation transcript:

1 计算机问题求解 – 论题 堆与堆排序 2018年05月14日 数据的组织（逻辑的，物理的）均可以影响到算法的设计和性能

2 如果我们要定义堆的ADT，在其数据部分，我们应该给出什么约束？
堆性质 如果我们要定义堆的ADT，在其数据部分，我们应该给出什么约束？ 树T 满足偏序树性质 当且仅当 树中任一结点的键值不小于（或不大于）其子结点（如果有）的键值。 树T满足几乎完全二叉性质 最底一层可能不满，但必须从左到右填充 就如栈一定是栈一样（用c来表示进入的过程），树也一定是树：用元素个数限制树的高度；用父子关系限制元素大小

3 问题1: 堆与我们上次讨论的队列与 栈最突出的差别是什么? 其特征与对象的内容相关, 一定是源于具体应用。
对象的内容决定了数据的存储和基本操作 对象的观察顺序决定了数据的存储和基本操作 其特征与对象的内容相关, 一定是源于具体应用。

4 问题2: 为什么我们常用数组来实现堆？ 偏序树性质在数组实现中如何表示？ 几乎完全性质在数组实现中如何体现？
一个nearly complete binary tree和一个数组是可以等价表示的。 树的基本概念均可通过数组的下标相关算法进行实现。 其中： 堆是一个nearly complete binary tree是关键 下标相关算法可以被实现为宏或者内联操作 在堆排序算法中，heapsize不断减少，但length没有改变 Parent(A.heapsize) <=A.heapsize/2

5 你能利用上图解释Max-Heapify吗？
特别注意一下largest Largest是潜在的冲突可能元素的下标，我们希望它成为以它为根的子树的最大 问题4: 你能利用上图解释Max-Heapify吗？

6 MAX-Heapify操作的pre/post-condition是什么？
Largest是潜在的冲突可能元素的下标，我们希望它成为以它为根的子树的最大 MAX-Heapify操作的pre/post-condition是什么？ Pre-condition: i的子女均已是某个大堆的根节点！ Post-condition: 以i为根，构成一个大堆！

7 Worst-case Analysis for Max-Heapify
过程Max-Heapify中不包含循环，所以，如果不递归，其代价是O(1)。 如果考虑比较运算的次数，每“下沉”一层，执行2次比较。 递归： 问题5： 为什么2n/3？ 左子树全满时：左子树几乎是右子树的一倍 此处的O(h)有伏笔

8 造“堆”：自底向上 问题6：这5个子树已经是“堆”了？ 其实后┌n/2┒个子树已经是“堆”了 其实算法循环从A.length开始又何妨？
分界线 问题6：这5个子树已经是“堆”了？ 其实后┌n/2┒个子树已经是“堆”了 对后一半数据进行heapify也是可以的，只是heapify的结果不会变化，没有意义 其实算法循环从A.length开始又何妨？

9 问题6： 这个循环的invariant是什么？ 循环过程中的第i次：i+1，…,n元素都是某个大堆的根。

10 Built-Max-Heap正确性证明

11 A Poor Upper Bound 问题7: 为什么这个Bound不很好？ 过于不tight了

12 关于堆的两点数学知识 N元素堆中，高度为h的子堆，最多有n/2h+1个 是什么意思？

13 建堆的时间复杂度是线性的 = O(2n) = O(n)

14 在堆中增加/删除一个元素，如何处理？ 放到数组中最后一个元素位置上，找它的父亲，交换或者不交换，如果交换发生，重复和父亲的比较，直到不发生交换。

15 堆排序 取出树根，和树的最后一个元素互换（将最后一个元素放到根上去），进行max-heapify。就地输出体现在“从小到大排序”，heap-size辖制max过程不会涉及到原来的根。 堆排序是stable的吗？不稳定

16 堆排序 算法部分正确性如何证明？ 每次进入循环时，A[i..A.length]都是升序排列的

17 堆排序算法： 问题9: 问题10： 怎么体现in-place, 即“原地输出”？
尽管堆排序时间复杂度是O(nlgn), 但快排算法似乎还是占有优势。为什么？ A[I..A.length]是有序的。 1，系数有差异； 2，数据访问时cache利用率不同

18 但堆作为一种性质鲜明的数据结构，仍然拥有很好的应用领域
堆数据结构的应用 堆排序似乎影响了堆的使用价值， 但堆作为一种性质鲜明的数据结构，仍然拥有很好的应用领域

19 问题11： 你能否通过比较priority-queue与一 般的queue，说明抽象数据类型(ADT) 对于计算机问题求解的意义？
同等优先级，FIFO；不等优先级，非FIFO；

20 Max-Priority Queue 抽象数据类型是为了减轻人思考的负担，而不是为了减轻计算机执行的负担。关键是如何实现！

21 实现：Array Heap Priority Queue

22 Open Topics： 1，通过实验和理论分析两种方法，比较堆排序和快排的性能和应用场景
2，用二叉树堆优先队列的方式给出优先队列的实现

23 家庭作业 TC pp.153-: ex.6.1-2, 6.1-4, 6.1-7 TC pp.156-: ex.6.2-2, 6.2-5, 6.2-6 TC pp.159-: ex.6.3-3 TC pp.160-: ex.6.4-2, 6.4-4 TC pp.164-: ex.6.5-5, 6.5-7, 6.5-9