本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-02 20:47:40

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

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

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

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

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

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

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