基本数据结构

堆

如果需要在动态变化的集合上取最大值或最小值，堆（heap）是非常合适的数据结构。

堆从逻辑上看可以看作是一个尽可能的满的二叉树，尽可能满的意思是只有最后一层可以不满，同时节点从左到右铺开。堆（最小堆）最重要的属性就是任意一个对象的要小于等于其孩子节点。对于同一个集合，有很多种方式构成一个堆，只要满足上述属性即可。

当实现堆的时候，通常使用数组来存储数据。数组中第 1 个对象是树的第一层，第 2-3 个对象是第二层，第 4-7 个对象是第三层，等等。如果用 $1,2,\cdots,n$ 来表示节点，那么对于第 $i$ 个节点，$\lfloor i/2\rfloor,i\geq 2$ 是其父节点，$2i,2i\leq n$ 和 $2i+1,2i+1\leq n$ 是其左右孩子节点。

插入操作比较简单。第一步保持近似满二叉树的形式，直接将新的对象插入到数组尾部就可以达到这个目的。第二步，保持堆的属性。将新插入的对象与父节点比较，如果比父节点小，那么与父节点交换，然后递归这个过程。一般将这个过程称为 Up BubbleUp HeapifyUp。如果有 $n$ 个对象，那么树的高度约为 $\log n$，那么新插入的时间复杂度是 $O(\log n)$。

删除最小对象的过程类似。第一步将最后一个对象移动到第一个对象的位置上，即把最小值删除掉了。第二步保持堆的属性。从根节点开始，比较当前节点和两个子节点的大小，如果有更小的子节点，将当前节点与最小的子节点交换，然后递归这个过程。这个过程一般称为 Down BubbleDown HeapifyDown。和插入类似，输的高度约为 $\log n$，那么删除最小对象的时间复杂度是 $O(\log n)$。

返回数组的第一个对象就能获取最大或最小对象，因此时间复杂度是 $O(1)$。

从 $n$ 个对象的数组开始直接建堆，除了挨个插入之外，还有一种更快捷的方式。从后往前，对前一半的对象调用 HeapifyDown 即可。时间复杂度是 $O(n)$。实现的时候外层循环是 $n/2$ 个对象，每次 HeapifyDown 是 $O(\log n)$，直观感受复杂度是 $O(n\log n)$。不过深入分析可以看出，$n/4$ 的对象最多下沉 1 层，$n/8$ 的对象最多下沉 2 层，以此类推，根节点只有一个，最多下沉 $\log n$ 层。从上往下看的话，第 $i$ 层有 $2^{i}$ 个节点，最多下降 $h-i$ 层。因此 $$S=1\cdot h+2\cdot (h-1)+\cdots+2^{h-1}\cdot 1$$ 这是一个等比等差数列求和，两边同时乘以 2 之后错位相减，那么 $$2S=2\cdot h+2^2\cdot (h-1)+\cdots+2^h\cdot 1$$ $$S=-h+2+4+\cdots+2^h=2^{h+1}-h-1=O(n)$$ 上式最后一步应用了 $n\approx 2^{h+1}$。

实现参考 Heap