基本数据结构

堆

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

堆从逻辑上看是一棵完全二叉树，只有最后一层可以不满，且该层的节点从左到右依次排列。堆（以最小堆为例）最重要的属性是任意一个节点的值都小于等于其子节点的值。对于同一个集合，只要满足上述属性，就可以构造出多种不同的堆。

实现堆时，通常使用数组存储数据。数组中第 1 个元素是树的第一层，第 2 至第 3 个元素是第二层，第 4 至第 7 个元素是第三层，依此类推。如果用 $1,2,\cdots,n$ 表示节点的下标，那么对于第 $i$ 个节点，当 $i\geq 2$ 时，其父节点的下标为 $\lfloor i/2\rfloor$，当 $2i\leq n$ 时，其左孩子节点的下标为 $2i$，当 $2i+1\leq n$ 时，其右孩子节点的下标为 $2i+1$。

插入操作比较简单。第一步是保持完全二叉树的形状，将新元素插入数组尾部即可。第二步是恢复堆的属性。将新插入的元素与父节点比较，如果它比父节点小，就与父节点交换，并重复这一过程。一般将这个过程称为 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$ 层。设树高为 $h$，从上往下第 $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$$ 又因为完全二叉树满足 $2^h\leq n<2^{h+1}$，有 $$S=-h+2+4+\cdots+2^h=2^{h+1}-h-1=O(n)$$ 所以建堆的时间复杂度为 $O(n)$。

实现参考 Heap