我一直在学习二叉堆,显然它是一个优先队列的好数据结构。假设我的数据流有数百万条(N)记录,我定期对排名前1000 (k << N) 的记录感兴趣。如果有足够的空间,我会维护一个大小为 N 的二叉堆,每次插入的复杂度都是 O (log N)。不过,我希望在每次插入时剪枝树,即丢弃第1001个元素。但是我并不清楚如何在少于O(k)的时间内进行剪枝。
(如果我对每次剪枝(和插入)的O(k)时间满意,我只需维护一个k个元素的有序列表而不是一个堆。)
一个想法是使用两个平行堆,一个保留最小值,另一个保留最大值,两个堆都只保留前1000个元素。不过这有点丑陋。
仅澄清一下,这些是我的限制条件:
- 插入:理想情况下少于~1000个操作(因此不适用原始列表) - 存储:有限的需要以插入速率大约剪枝不受欢迎的项目(某些恒定的开销是可以接受的) - 询问前1000名:前1000名不必完全排序,堆式顺序可以
(如果我对每次剪枝(和插入)的O(k)时间满意,我只需维护一个k个元素的有序列表而不是一个堆。)
一个想法是使用两个平行堆,一个保留最小值,另一个保留最大值,两个堆都只保留前1000个元素。不过这有点丑陋。
仅澄清一下,这些是我的限制条件:
- 插入:理想情况下少于~1000个操作(因此不适用原始列表) - 存储:有限的需要以插入速率大约剪枝不受欢迎的项目(某些恒定的开销是可以接受的) - 询问前1000名:前1000名不必完全排序,堆式顺序可以