高效优先级列表

Question

高效优先级列表

javaalgorithmpriority-queue

5

我正在寻找一种高效的数据结构来表示优先级列表。具体而言，我需要为一组项目分配优先级，并仅返回得分最高的项目。我已经研究了基于堆的优先队列，但它们似乎并不真正适合我的需求。它们将在我从队列中轮询顶部评分项目时重新组织堆结构。

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

有没有更好的解决方案？

- ladi

有多少个项目？它们是否被持久化在任何地方，如果是，如何持久化？ - Lazarus

5

请进一步阐述您希望相对于彼此而言，插入、检索（优先项目）和删除操作的效率要求是怎样的。 - Artelius

我想先对项目进行评分，然后按正确顺序检索前x个得分最高的项目。因此，由于存在许多插入操作，插入应该相当高效。检索可能不太高效。 - ladi

x 和 n 相比较如何？ x <= 100 吗？ x 接近 n/2 是什么意思？ - Aryabhatta

1

堆是完成这个任务的标准方式，但您似乎反对在删除顶部元素时重新排序堆内容。为什么会有问题？您真正想要做什么？ - andand

5个回答

4

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

- Maciej Piechotka

如果使用正确，堆比跳表更好。当您需要前x个元素时，请使用x个元素的最小堆。您不必构建所有n的树/堆，只需x个即可。 - Aryabhatta

抱歉 - 是我的错，我误读了文本（我理解他想要快速轮询，即使牺牲了慢速添加）。 - Maciej Piechotka

4

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

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

因此，如果您随机生成元素，则性能很可能非常好。即使您生成排序的项目（最坏情况），也可能对于您的k值而言速度足够快。

- Mau

1

如果您使用min-heap（请参见我的答案）而不是列表，则最坏情况时间为O（logK）。其余部分类似。实际上，像这样使用min-heap对于解决此问题非常标准！（当x相对于n很小时）。 - Aryabhatta

1

JDK内置了一个pqueue类(java.util.PriorityQueue)，它基于堆算法。

抱歉，我刚才才看到堆不符合您的需求的部分。您能解释一下原因吗？您可以编写自定义比较器（或使您的项目可比较），PriorityQueue将适当地对您的项目进行排序。

- dty

据我理解，他认为在O(log n)中找到getNext是不可接受的。 - Maciej Piechotka

1

问题似乎在于 Ladi 希望能够获取前 x 个项目，而无需删除任何项目。这通常不是优先级列表支持的操作。 - Michael Borgwardt

我想对一些项目进行评分，并仅获取得分最高的前n个项目。因此，我想知道是否有任何数据结构仅保留得分最高的项目，但提供列表接口。这意味着我可以按顺序浏览得分最高的项目列表。当然，我可以使用基于堆算法的优先队列，它具有O（log n）插入和O（n）检索，获取得分最高的元素并将它们添加到列表中。我只是好奇是否存在比这更好的东西。 - ladi

1

@ladi：不确定您所说的O(n)检索是什么意思——从堆中提取顶部项的时间复杂度为O(log n)。只有当您需要查找特定（非最小）元素时，检索才是O(n)。如果您只能比较两个项目并确定哪个更大，则在您所看到的问题上，没有任何渐近快于堆的方法。 - j_random_hacker

0

一棵平衡树总是能保证最坏情况下的对数时间复杂度。虽然线性时间通常被认为是可行的，但对数时间和线性时间之间仍存在巨大差异：对于十亿个元素，差异在于10亿次操作和几十次操作之间。如果每个操作需要1毫秒，那么从11天到不到1秒。

每个节点最多有两个子节点。
堆树是完全且左调整的。完全意味着如果堆的高度为H，则每个叶节点位于级别H或H-1。所有级别都是左调整的，这意味着没有右子树的高度大于其左兄弟。因此，如果一个叶子与内部节点处于相同的高度，则该叶子不能在该节点的左侧。
每个节点保存其子树中具有最高优先级的值。

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

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

参考

- Yilmaz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

堆似乎非常合适，但你的做法好像有些错误。假设你想要前x个元素（顺便问一下，这个x和n相比怎么样？），你正在将所有元素放入最大堆中，并获取前x个。

我建议你使用恰好x个元素的小根堆代替。将前x个元素插入堆中。下一个到来的元素，与堆中的最小值进行比较，可以在O(1)时间内快速完成（在堆中）。如果比最小值小，则忽略该元素。如果进来的元素比最小值大，则将最小值增加到进来的元素并在堆中下移。在最坏情况下，这应该是logx时间。一旦完成（在nlogx时间内），您可以以O(xlogx)的时间按排序顺序从堆中检索元素。根据数据情况以及x的大小如何，使用此小根堆解决方案可能非常快。

如果你真的非常想让插入操作超级快，并且不太关心检索操作，那么你也可以采用以下方法。将元素按照它们出现的顺序插入向量（具有平摊O(1)插入时间的数组）。然后使用选择算法查找第x大的元素（在O(n)时间内完成，但常数可能很大）。假设该数字为S。现在遍历数组，将每个元素与S进行比较，并选择与S一样大的元素。如果x相对于n而言比较小（例如n/2之类的），那么这种方法可能很好用。但是，如果x相对于n而言很小，我建议还是使用小根堆。