java - 高效的优先级列表

Question

我正在寻找一种有效的数据结构来表示优先级列表。具体来说，我需要为一组项目分配优先级，并且只返回得分最高的项目。我研究了在堆上运行的优先级队列，但它们似乎并不真正适合我的需要。一旦我从队列中轮询最高评分项目，他们就会重新组织堆结构。

最简单的解决方案当然是链表，在最坏的情况下，插入操作需要很长时间。

有没有人有更好的解决方案？

Answer 1

堆似乎非常合适，而且看起来你做错了。

假设您想要前 x 个元素（这个 x 与 n 相比如何，顺便说一句？）

您正在做的是将所有内容放入最大堆并获得顶部 x。

相反，我建议您使用恰好 x 个元素的最小堆。

您插入堆的第一个 x 元素。

下一个传入元素，您将与堆中可以非常快速（O（1）时间）完成的最小值进行比较。如果更小，您只需忽略传入的元素。

如果传入元素大于 min，则将 min 增加到传入元素并将其筛选到堆中。这应该是最坏的 logx 时间。

完成后（在 nlogx 时间内），您可以在 O(xlogx) 时间内按排序顺序从堆中检索元素。

根据您的数据如何（以及 x 有多小），使用此最小堆解决方案可能会非常快。

---

如果您真的希望插入速度非常快并且不太关心检索，那么您也可以执行以下操作。

按照它们出现的顺序将元素插入向量（具有分期 O(1) 插入时间的数组）中。

使用选择算法找到第 x 个最大的元素（在 O(n) 时间内，但常数可能很大）。假设这个数字是 S。

现在遍历数组，将每个元素与 S 进行比较，并选择与 S 一样大的元素。

如果 x 的大小合理并且与 n 相当（如 n/2 或其他东西），这可能会很好，但如果 x 与 n 相比较小，我建议使用最小堆。

Answer 2

唔。跳过列表？他们应该有 O(log n) 插入（作为基于堆的队列），但获取顶部元素应该是 O(1) [包括删除它]。它们甚至可以使用无锁算法来实现。

Answer 3

如果您只需要前k个项目而无需查看其他项目，则可以使用仅存储当前前k个项目的简单链表或数组，加上一个数字（列表中元素的最差分数）。

在Add()操作中，您只需将项目与列表中的最差值进行比较，如果更好，则将当前最差的值与添加的项目交换。在最坏的情况下，插入需要O(k)时间，因为您需要找到当前得分最差的元素。然而，平均情况是O(1)，因为当您向列表中添加更好的元素时，必须进行交换的概率趋于 0（也就是说，您实际上并没有添加任何项目）。

所以如果你随机生成元素，你的表现很可能会非常好。即使您生成已订购的商品（最坏的情况），它也可能对您的k值足够快。

Answer 4

JDK 有一个基于堆算法的内置 pqueue 类 (java.util.PriorityQueue)。

抱歉，我只看到了一些关于堆不符合您的需求的信息。你能解释一下为什么吗？您可以编写自定义比较器（或使您的项目具有可比性），PriorityQueue 将适当地为您的项目排序。

Answer 5

平衡树总是保证对数最坏情况。尽管通常认为线性时间是可行的，但对数和线性之间仍然存在巨大差异：

对于十亿个元素，差异在十亿个操作和几十个之间。如果每个操作需要 1 毫秒，这意味着从 11 天缩短到不到一秒。

• 每个节点最多有两个孩子。

• 堆树是完整的并且是左调整的。完全意味着如果堆的高度为 H，则每个叶节点要么处于 H 级，要么处于 H-1 级。所有级别都是左调整的，这意味着没有右子树的高度大于其左兄弟。因此，如果叶子与内部节点的高度相同，则叶子不能位于该节点的左侧。

• 每个节点在以该节点为根的子树中拥有最高优先级。

二叉搜索树是最常见的树，但我们可以使用二叉树。我们可以使用任何大于 2 的值，并为堆使用相同的数组表示。

但是我们对树木的改进是有代价的。首先，与任何使用指针的数据结构（列表、图形、树等）一样，与数组相比，我们有内存开销。而对于后者，我们只需要为数据保留空间（加上可能，根据实现细节，指针和节点结构本身的一些常量空间），每个树节点都需要额外的空间来存储指向其子节点的指针，并且可能它的父母。