堆 #
作为数据结构的定义，二叉堆是一种数组对象，可以看作一棵完全二叉树。
将数组元素按下标顺序填充到树中，树的填充顺序从上层到下层，从左到右，逐层填满。
数组第一个元素是根节点，数组最后一个元素是树的最下层的最右叶子节点。
对应树的节点和左右子节点的关系在数组A中的对应位置：如数组中，元素 i（A[i]）的左子节点为 A[2*i + 1]，右子节点为 A[2*i+2]
注：本文讨论的数组下标 i 的取值从0开始。
最大堆 #
在堆中，每个节点都不小于它的子节点，那么这个堆就是最大堆。
即 A[parent(i)] >= A[i]。
根据上面的定义，对于数组中的元素，如果要称为最大堆：
- A[i] >= A[2*i+1] (如果 2*i+1 越界，那么A[i]是叶子节点，也符合最大堆的定义)
- A[i] >= A[2*i+2] (如果 2*i+2 越界，那么A[i]没有右子节点，比较上面一个即可)
通过上面的内容，我们可以看出，最大堆的根节点是值最大的元素。
要实现最大堆，需要从数组第 length(A)/2 个元素开始到第0个元素（不用比较 length(A)/2 + 1 之后的元素，是因为这些元素一定是叶子节点），通过上述定义的比较，如果该节点不小于左右子节点，那么就往前一个元素比较。
如果有左右子节点比改节点的值大，那么选最大的子节点(记为largest)，交换值，然后对largest节点做比较过程，直到满足条件。
这个构建最大堆的过程，时间复杂度为 O(lgn)。
类似的，如果每个节点都不大于它的子节点，那么这个堆就是最小堆。
二叉堆有两种，就是上面提到的最大堆和最小堆。
堆排序 #
我们讨论基于最大堆的排序。
基本思想和步骤：
- 构建一个最大堆，那么它的根元素一定是最大的
- 把根节点取出来，换一个元素作为根，再经过一次构建最大堆的过程，那么会得到第二大的值
- 重复这个过程
这样，就实现了排序。
取什么值来替换根是一个问题，比如取左子节点？逻辑上是比较合适的，根据最大堆的定义，左子节点下面的树不用比了，而右子节点是它下面树的最大值，两个选一个最大的就能得到第二大。但是把左(或右)子节点移动为根，会涉及数组内大量元素的移动。
取堆最后一个元素与根交换是比较合适的。这样只需要移动一个元素，并且不需要引入新的存储空间(引入常量空间，而不需要引入与数组元素数量相关的存储空间)。
最终会在原数组实现元素值的顺序排列。
堆排序的时间复杂度是O(n lgn)。
应用场景 #
最大(小)堆应用场景：
- 排序
- 时间复杂度 O(n lgn)
- 最大/小优先级队列
- Insert(S, x)，插入元素x到S，时间复杂度 O(lgn)
- Maximun(S)，返回S中最大值元素，时间复杂度 O(1)
- Extract-Max(S)，去掉并返回S中最大值元素，时间复杂度 O(lgn)
- Increase-Key(S, x, k)，将元素x到值增加到k (k>S[x])，时间复杂度 O(lgn)