该文章为Princeton-Algorithms Part I读书笔记，相关视频在此。
1. PQ的API接口
PQ的API接口
关键：能够找到最大（最小）的元素，能够删除最大（最小）的元素。
2. 应用的例子
目标：在包含M个元素的stream中求最大(最小)的k个
限制：没有足够的空间一次性装下所有M个元素，因此不能对所有元素进行sort。
pq的应用-求top k
关键：及时排除不可能的元素
3. PQ的几种实现方式
PQ的几种实现方式
由于sort实现会违反对存储空间的约束，因此排除这个想法。
4. 实现1：Elementary实现
- 利用unordered array：插入的时候简单在结尾append，要删除的时候遍历所有，找到要删除的元素。
- 利用ordered array：插入的遍历所有找到相应的位置，删除的时候直接在结尾删除。
Paste_Image.png
但是目标是：插入，删除与查找都要比较高效。
5. 实现2：Binary Heap实现
属于一个complete binary tree，tree中节点具有以下属性：每个节点的优先级都不小于其子节点的优先级。
5.1 Binary Heap的表示：数组
因为完全二叉树具有结构上的紧凑型，实际上的可以用数组来进行表示。
Binary Heap的数组表示
5.2 性质：
- Parent's key no smaller than children's keys.父节点Key总是要大与孩子的节点，这很重要！在插入和删除操作中要维持这个不变性。
- 数组的遍历就是Heap level order遍历
- Largest key is a[1], which is root of binary tree.
- Parent of node at k is at k/2.
- Children of node at k are at 2k and 2k+1.
5.3 插入操作
- 思路：插入到最后位置，然后根据情况上移
- 效率：O(lgN)
5.4 删除最大(最小)操作
- 思路：将最后的节点补到被删走的根节点处，然后根据情况下移
注意：下移的时候，只与较大的子节交换
- 效率：O(lgN)
6. 由Heap引出的排序算法：Heap Sort
6.1 基本思想
- 将要排序的N个元素建成heap
- 反复取出最大的元素
6.2 步骤1：由一个random ordered数组建heap
- 思想：采用自底向上的方法，先保证3个元素的heap是ordered的，再保证7个元素的heap，以此类推直到处理完整个heap。
- 效率：因为在整个过程中
6.3 步骤2：反复取出最大的元素，在数组尾部由后往前填
- 思路：反复将root的元素与最后一个元素交换。交换后，根据情况下移。
6.4 效率
- 建heap：根据数学方法，可以证明为线性O(N)！
- 交换元素+下移：O(nlgn) -> N次交换，每次交换后最多下移lgN
Heap Sort的优势在于：in-place排序，而且worst case才是NlgN
对比：
- Merge Sort：需要额外空间
- Quick Sort：worst case可能达到O(N^2)
6.5 缺点
- unstable
6.6. 排序算法总结
排序算法总结
