对顶堆

· · 个人记录

对顶堆可以处理动态第 k 大等问题（k 是常数）。

如果不用对顶堆，我们可以用平衡树解决这个问题，但是常数一般比前者大 2~3 倍（我的实现）。

对顶堆实际上是两个堆，一个大根，一个小根。每个堆自己的单调性是显然的，而我们同样要维护堆之间的单调性：小根堆的最小是大于大根堆的最大的。

就算这样又怎么样？没法怎么样。为了快速得到第 k 大，我们需要保证大根堆里头只有 k - 1 个元素。这样，每一次我们取小根堆的头就可以了。

如果要维护动态中位数，也是可以的，只需要保证两个根的大小差是不超过 1 的即可，中位数就是较大的堆的根。

有人将对顶堆形容为一个沙漏，让人印象很深。但是，如果看成是两个梯形躺在地上，左边是大根堆，右边是小根，中间是分界线，而小根的顶大于大根的顶，应该更形象。

于是我们就维护出了动态第 k 大。