我一直在研究二进制堆，它们显然是优先级队列的一个很好的数据结构。假设我的数据流有数百万 (N) 条记录，并且我定期对排名前 1000 (k << N) 条记录感兴趣。如果有足够的空间，我只需维护一个 N 大小的二进制堆，每次插入的时间复杂度为 O(log N)。不过，我想做的是在每次插入时修剪树，即丢弃第 1001 个元素。对于我来说，如何在小于 O(k) 的时间内进行修剪并不明显。
（如果我对每次修剪（和插入）的 O(k) 时间感到满意，我只需维护 k 个元素的有序列表，而不是堆。）
一种想法是有两个并行堆，一个保留最小值，另一个保留最大值，两者都只保留前 1000 个元素。不过，它有点难看。
只是为了澄清一下，这些是我的限制：