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

Question

我需要一个始终包含n迄今为止插入的最大项目的数据结构(没有特定的顺序).

所以,如果n是3,我们可以进行以下会话,其中插入一些数字并且容器的内容发生变化:

[]  // 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_queuefor元素(委托),它使用反向比较,因此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],最小的元素),并拒绝它
  • 用新元素替换它(A [1]:= x)
  • 现在,恢复堆条件:
    • 如果x小于或等于它的两个孩子,你就完成了
    • 否则,与最小的孩子交换x
    • 在每个新位置重复测试和交换,直到满足堆条件

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

Answer 2

在Java中,您可以使用例如由TreeSet实现的SortedSet.每次插入后检查集合是否太大,如果是,则删除最后一个元素.

这是相当有效的,我已经成功地使用它来解决几个项目欧拉问题.