10. 堆，优先队列与堆排序

堆

我们将一棵树变得更加特别，即限制其必须为完整的，即每一个树的层级都是满的，除了最后一层。
然后，我们联想生活中的常见的堆型结构：稻草堆，其特征是上小下大，那么，我们就可以定义数据结构中堆的特性：具有一定的偏序关系(优先级)，且根节点的值总是该偏序关系的一端。

堆的节点关系

堆在内存中存储为一个 array 的形式，假设当前节点的 index 为 i (假设根节点 id = 1):

• 父节点 i / 2
• 左子节点 2i
• 右子节点 2i + 1
• 是否为叶节点 return (2 * i > n)

大顶堆的实现

fixUp()

当我们向一个堆进行插入元素操作，那么我们需要保证堆的特性，即根节点的值总是最大的。我们可以通过将新插入的元素与其父节点进行比较，如果新插入的元素大于其父节点，那么我们就将新插入的元素与其父节点进行交换，直到新插入的元素不再大于其父节点。
这个操作的结果是 将新的堆变成符合 父节点大于子节点的属性，且根节点一定是顺序最高的

fixDown()

当我们删除堆顶的元素的时候，我们需要将下面的元素逐个选择大的向上填充，那么我们就需要进行 fixDown() 操作，即将当前节点与其子节点进行比较，如果当前节点小于其子节点，那么我们就将当前节点与其子节点中最大的进行交换，直到当前节点不再小于其子节点。
在删除的时候，将当前堆底的元素放到堆顶，然后进行向下沉淀，直到堆顶的元素不再小于其子节点。

时间复杂度

我们在使用 heap 进行 push 或者 pop 的时候，都要进行 fixUp 或者 fixDown 操作，因此时间复杂度都是 $\log n$

如何区分两种方法？

观察 fixUp 操作，其只会选择从 一个 leaf 节点不断向上走，找到最后的根节点（或者不发生交换的地方），路径是唯一确定的，不会影响其他已经完成排序的部分; 而 fixDown 操作会将 root 不断向leaf 寻找，路径不一定，直到不发生交换

堆排序

堆排序包括两个步骤：1. 对数组堆化 heapify, 2. 对堆进行排序

heapify 堆化

假设现在有一个 array 的输入，尺寸为 n 那么这个输入步骤的时间复杂度怎么计算呢？
如果把输入存储的结构看作一个 堆，那么我们会对每一个输入进行 fixUp 操作，那么就是 $O(\log n)$ 复杂度，这样一共输入了 n 个元素，就是 $O(n\log n)$ 复杂度

Bottom_Up + FixDown 方法

在 std::make_heap() 函数中使用了一种复杂度为 $O(n)$ 的堆化方法
在这个算法中，我们从叶节点开始，逐步向上走，并且对每个节点做 fixDown 操作（这个操作就是做到叶子节点）这样就可以保证堆的顺序。
乍一看这个方法好像也是 $n\log n$ 但是，由于叶子节点是不需要考虑的，因此我们实际上至多考虑 $n / 2$ 个节点
找规律完成递推，我们发现一级节点(leaf 上面一级) 的交换次数最多一次，有 n / 4 个，二级节点交换最多2次，有 n / 8 个，三级节点交换最多三次，有 n / 16 个，以此类推，最后一级节点log n 次 （因为每一层选择最大的子节点进行交换），因此我们可以得到一个递推公式：

$\sum_{i = 1}^{log n} \frac{n}{2^i} \times (i - 1) = O(n)$

然后我们简单的看一下发现之小于 n ，即复杂度 $O(n)$

堆排序

我们可以从选择排序中受到启发，每次选择最大的放到最后这个操作，因为堆的存在提供了较大值靠前，最大值在堆顶这么一种特性，因此我们很容易就能找到最大值，那么我们只需要不断执行 top() -> end() 就行，但是这还缺少一步，就是我们事实上在 堆顶删除了一个元素，那么我们需要将第 size - 1 个元素取出来放到堆顶然后做下沉操作，这样就能保证堆的顺序。
这个每一步的复杂度(取决于 fixDown)都是 $O(\log n)$ 且要重复 n 次，再加上前面堆化的时间复杂度是 $O(n)$, 因此总的时间复杂度是 $O(n\log n)$
这个算法本身并不需要额外空间(在原数组空间内完成)，因此空间复杂度是 $O(1)$

优先队列

优先队列是以堆结构实现的一个数据结构，其能保证优先级高的排在前面，因此，我们在定义的时候，需要加入一个比较函数，来保证优先级的比较。
在 c++ 中，这个比较函数一般使用仿函数 functor 或者 lambda 表达式来实现（lambda 表达式 和 js 中的伪函数临时函数写法很像）

代码定义

std::prior_queue<your_type, std::vector<your_type>, CompareClass> pq;

注意这里仿函数输入的是类而不是对象
注意如果仿函数存在两种情况优先级一定的情况，这会很危险，因为优先队列对于同优先级的顺序是不一定的，为了可控我们需要将一些优先级变得更高

优先队列的操作

优先队列内置了fixUp, fixDown 等操作，因此我们并不需要在push 之后手动执行排序操作，而是默认程序会自动完成之