该文章为清华大学数据结构与算法设计MOOC课程读书笔记.
1. 接口
PQ的接口
PQ中有引入了一个重要概念：优先级Priority
2. 实现
2.1 实现1：向量，列表
无序(有序)向量实现以及无序(有序)列表实现都不能兼顾地给出高效的三种操作。
2.2 实现2：完全二叉堆complete binary heap
由完全二叉树组成，因为其结构上的紧凑型，实际上的可以用向量来进行表示。因此，完全二叉堆：
- 逻辑上，等同于完全二叉树。
- 物理上，等同于向量。
3. 插入操作
- 思路：插入到底层，上滤
- 效率：O(lgN)
4. 删除操作
- 思路：拿走堆顶元素，替换为末元素，下滤。
- 效率：O(lgN)
注意：下滤的交换对象为相对较大的子节点
5. 建堆操作
思路1：自上而下的上滤
- 方法：将数组由做往后填，当需要上滤时进行上滤。
- 效率：O(NlgN)
理解tip：考虑最底层节点，数目为N/2的数量级，每个节点最多会上移lgN。其实就是对所有节点深度的求和。
思路2：自下而上的下滤
- 方法：将数组由后往前考虑，当需要下滤时进行下滤。
- 理解：相当于对子堆的逐层合并！
- 效率：数学方法可以证明达到O(N)
理解tip：由于效率取决于总的下移次数。对于每个节点，其下移次数最多为其高度，因此Sum = lgN + 2lg(N-1) + 4lg(N-3) + .. + 1 = O(N)。区别于思路1，这里是对所有节点高度的求和。
6. 堆排序
思路：
建堆 + 不断取出最大值 + 维护堆序
时间效率：
O(n) + n * O(lgn) = O(nlgn)
理解：类似于选择排序，但是在利用堆的特性，使得选择的过程变得更快！
空间效率：O(1) - in place！
堆排序效率
7. 堆的扩展-左式堆
7.1 目的
左式堆的引入是为了完成高效的堆合并
7.2 堆合并的几种思路
思路1：将其中一个堆逐一取出，然后逐一加到另一个堆
- 效率低O(mlg(m+n))
思路2：将两个堆的元素拿来直接建一个堆
- 线性效率 O(m + n)- 虽然效率可以接受，但是却没有利用本来两个堆各自有的有序信息。
思路3：左式堆
- 效率：O(lgn)
- 理解：尽可能利用原先两个堆的有序性，尽可能地减少对节点的操作！
7.3 什么是左式堆？
满足左倾性的堆就是左式堆
-
空节点路径长度
Null Path Length 左倾性：任何节点右孩子的NPL不超过左孩子
左倾性
- 右侧链 - 左式堆的右侧链长度为O(lgN)
右侧链
7.4 左式堆合并算法
思路：
合并A的右子堆和B
实现
左式堆合并实现
效率：
因为一直在操作右子堆，因此效率上与右侧链长度同数量级，即O(lgN)
