language-agnostic - 始终保持 n 个最佳元素的数据结构

Question

我需要一个始终保存 n 的数据结构迄今为止插入的最大项目(无特定顺序)。

所以，如果 n是 3，我们可以在下面的 session 中插入一些数字并且容器的内容发生变化:

[]  // now insert 1
[1] // now insert 0
[1,0] // now insert 4
[1,0,4] // now insert 3
[1,4,3] // now insert 0
[1,4,3] // now insert 3
[4,3,3]

你明白了。数据结构的名称是什么？实现这一点的最佳方法是什么？或者这是在某个图书馆？

我正在考虑使用具有 priority_queue 的容器对于它的元素(委托(delegate))，它使用反向比较，所以 pop将删除最小的元素。所以 insert函数首先检查要插入的新元素是否大于最小元素。如果是这样，我们将最小的元素扔掉并推出新元素。

(我有一个 C++ 的实现，但问题与语言无关。)

Answer 1

您想要的特定数据结构可能是隐式堆。原始数据结构只是一个数组；为方便起见，假设它的大小为 N=2^n 个元素，并且您希望保持最大的 N-1 个元素。

这个想法是将数组(称为 A)视为深度为 n 的完整二叉树:

忽略 A[0]；将 A[1] 视为根节点

对于每个节点 A[k]，子节点是 A[2*k] 和 A[2*k+1]

节点 A[N/2..N-1] 是叶子

要将树维护为“堆”，您需要确保每个节点都小于(或等于)其子节点。这称为“堆条件”:

A[k] <= A[2*k]

A[k] <= A[2*k+1]

要使用堆来维护最大的 N 个元素:

请注意，根 A[1] 是堆中的最小元素。

将每个新元素 (x) 与根进行比较:如果它更小 (x

否则，将新元素插入堆中，如下所示:

从堆中删除根(A[1]，最小元素)，并拒绝它

用新元素替换它 (A[1]:= x)

现在，恢复堆条件:

如果 x 小于或等于它的两个 child ，你就完成了

否则，将 x 与最小的 child 交换

在每个新位置重复测试和交换，直到满足堆条件

基本上，这将导致任何替换元素“过滤”树，直到它达到其自然位置。这最多需要 n=log2(N) 步，这是你能得到的最好的。此外，树的隐式形式允许非常快速的实现；现有的有界优先级队列库很可能会使用隐式堆。