高效优先级列表

堆看起来很合适,而且你好像在做错事。

假设您想要前x个元素(这个x与n,btw相比如何?)

你要做的就是把所有的都放到一个max堆中,然后得到顶部的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小,我建议使用min堆。

隐马尔可夫模型。 Skip lists ?它们应该有O(log n)插入(作为基于堆的队列),但是获取top元素应该是O(1)[包括删除它]。它们甚至可以使用无锁算法实现。

如果你只需要 K 最重要的项目和你 从未 需要看其他的,你可以使用一个简单的链表或数组,只存储当前的顶部 K 项目,加上一个数字(列表中元素的最差分数)。

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

因此,如果您随机生成元素,那么您的性能可能非常好。即使您生成已订购的项目(最坏的情况),它也可能足够快,足以满足您的价值 K .

JDK有一个基于堆算法的内置PQueE类(java. U.L.PrryTyQueLead)。

对不起,我只看到堆不符合你的需要。你能解释一下为什么吗?您可以编写一个定制的比较器(或者使您的项目具有可比性),PriorityQueue将对您的项目进行适当的排序。