9

我需要一个始终保存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_queue它的元素（委托）使用反向比较，因此pop将删除最小的元素。因此该insert函数首先检查要插入的新元素是否大于最小元素。如果是这样，我们将最小的元素扔掉并推出新元素。

（我有一个C++实现，但问题与语言无关。）

4

8 回答 8

14

您想要的特定数据结构可能是隐式堆。原始数据结构只是一个数组；为方便起见，假设它的大小为 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) 个步骤，这是你能得到的最好的。此外，树的隐式形式允许非常快速的实现；现有的有界优先级队列库很可能会使用隐式堆。

于 2009-02-19T06:50:34.757 回答
5

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

这是相当有效的，我已经成功地使用它来解决几个 Project Euler 问题。

于 2009-02-19T07:30:58.963 回答
4

priority_queue 是 C++ 中最接近 STL 的东西。您可以将其包装在另一个类中，以创建您自己的实现自动修剪大小。

与语言无关（尽管可能不是安全的内存碎片）：

  1. 插入数据
  2. 种类
  3. 删除第 n 个元素之后的所有内容

std::priority_queue 为您执行第 2 步。

于 2009-02-19T06:15:23.780 回答
2

一个有界的优先级队列，我认为...... Java 在其标准库中有类似的东西。编辑：它被称为LinkedBlockingQueue. 我不确定 C++ STL 是否包含类似的东西。

于 2009-02-19T06:07:08.917 回答
1

难道不能只从排序集合中获取前 n 个元素吗？

于 2009-02-19T07:30:42.333 回答
1

在 Pyhton 中，使用 heapq。在它周围创建一个小包装器，如下所示：

class TopN_Queue:
    def __init__(self, n):
        self.max_sz = n
        self.data = []

    def add(self, x):
        if len(self.data) == self.max_sz:
            heapq.heappushpop(self.data, x)
        else:
            heapq.heappush(self.data, x)

...

于 2018-09-28T03:44:43.223 回答
0

是的，您可以保持最小的大小为 N，然后在每次插入时将新项目与根项目进行比较

于 2012-11-21T07:46:11.880 回答
-1

创建一个最小堆，同时存储一个计数器。

每当到达计数器时；提取分钟。

您可以这样做：O(1) insert、get-min 和 O(log log n) extract-min。[1]或者，对于其他提到的操作，您可以使用 O(log n) 插入和 O(1) 来执行此操作。[2]

[1]M. Thorup，“Integer priority queues with reduction key in constant time and the single source shortest paths problem”，第 35 届 ACM 年度计算理论研讨会论文集，纽约，纽约，美国，2003 年，第 149 页–158。

[2]GS Brodal、G. Lagogiannis、C. Makris、A. Tsakalidis 和 K. Tsichlas，“指针机中的最佳手指搜索树”，J. Comput。系统。科学，卷。67，没有。2，第 381-418 页，2003 年 9 月。

于 2013-01-05T09:30:13.943 回答