堆
堆简述
堆（heap）的结构是一个完全二叉树的结构。
堆分大根堆和小根堆。如果一个二叉树它即不是大根堆，也不是小根堆，那它不是堆。
大根堆：每一个根节点，都大于它的两个子节点。
小根堆：每一个根节点，都小于它的两个子节点。
注意，大根堆和小根堆并不能保证在不同分支上它们的大小关系有规律。
树的高度为 logN（可以发现每一层満时它在此层 i 的元素个数为 2^i）。
完全二叉树，每个节点最多有两节点，完全二叉树中，每一层或是満的，或是从左到右依次变満的状态。
参考：https://visualgo.net/en/heap
堆的实现
堆可以用数组实现。
[0, 1, 2, 3, 4, 5] 可依次从上到下，从左到右填入完全二叉树中。
数组放入完全二叉树
则数组下标中 i 位置，它寻找节点的关系为
- 父节点：(i - 1) / 2；
- 左子节点：2 * i + 1；
- 右子节点： 2 * i + 2；
有时，常常为了方便，将数组下标 0 的元素弃而不，所以当 i' 从 1 开始时，则对应关系为：
- 父节点：i' / 2；
- 左子节点： 2 * i'；
- 右子节点： 2 * i' + 1；
不用 0 元素，是因为在找下标时很容易用移位（>> 或 <<）的方式找到关联的下标位置。
而对 0 移位操作得到的结果始终为 0，不方便找寻相关节点的下标。
2 * i + 1 = i << 1 | 1
维护大根堆
小根堆与大根堆规则一样，不再缀述。
请参考 https://visualgo.net/en/heap 中的演示。
添加过程
所以，构建大根堆的过程：
- 将此数放在堆的最后一个位置
- 将此数与其父节点比较，大则交换，小则停止
- 重复第二步骤，直到此数找到合适的位置
因为添加每一个元素它移动的步数正好为二叉树的高度，所以每一步的复杂度 logN。
移除堆中的最大值后调整以维持大根堆（heapify）
方法：将最后一个值放到移除的位置（原来最大值的位置），让最小值向下沉，直到找到合适位置。
步骤：
- 将最末值 Z 放入最大根位置（树顶）；
- 堆空间大小（heapSize）减 1；（用一个变量来维护的堆的大小）
- 将 Z 分别与其子节点比较，若 Z 小，则与大者交换，若 Z 大于所有的子节点或无子节点则停止；
- 重复上一步过程，直到 Z 停止移动。
堆排序
堆排序是指，给定一个数组，然后将此数组构建成堆（这里为大根堆），然后将它排序成从小到大的顺序。
方法一
有了上方维护大根堆过程的原理后，这个方法就很好理解了：
- 将数组构建成大根堆；（
O(N*logN)） - 将堆的最大根与最末值进行交换（最大值放到最末）；
- heapSize - 1 （已放到最后的最大值不再比较）；
- 将此时的堆空间进行 heapify；（
O(logN)） - 重复上述 2 - 4 步骤，直到 heapSize 等于 1；（
O(N)）
此时整个数组就变成了已排序的了。
时间复杂度 O(N*logN) + O(logN) * O(N) => O(N*logN)
方法二
在方法一上进行优化。优化点是在数组构建成大根堆的过程上（也就是方法一的步骤 1 中）。
数组构建为大根堆优化版思路总述：将数组看成一个完全二叉树，从下往上开始，保证每一个子树为大根堆（小值下沉的方法），最后得到一个大根堆。
步骤：
- 二叉树最底层每一个元素均为一个大根堆
- 二叉树倒数第二层每一个元素与其子元素比较，利用上方的小值下沉的方法，使其每个元素与其子节点为大根堆
- 重复以上步骤，判断倒数第 k 层，使其每个元素作为父节点成为大根堆，直到 k 表示为顶层。
这其中，不用判断最后一层，只需要用下标从 N-1 变到 0 即可。
这种方法将构建大根堆的时间复杂度优化为 O(N)。
小结：构建堆，自上而下的方法时间复杂度为 O(N*logN)，自下而上的方法时间复杂度为 O(N)。
面试题：几乎有序的数组的排序
几乎有序是指，若将数组排好顺序，每个元素移动的位置不超过一个常数 k。
思路，这个题就可以用堆（具体是小根堆）来做。根据题意，要得到的排序结果在 i 位置上的数一定是在 i - k 到 i + k 之间，所以有 2k + 1 个可能。但从第一个元素开始放入正确的值时，后面每一个位置的可选项只有 k + 1 个。所以堆的大小是 k + 1，每 k + 1 个数放满小根堆后就可以确定第一个小值所在的位置。堆不满而元素已放完时，从剩下堆中选即可。
复杂度，O(N*logk)
