当从大列表中获取最大的n个元素时，应该使用哪种算法？

Question

在我的项目中，有一个非常大的列表。这个列表中最常见的操作是获取最大的n元素。在整个生命周期中，n是固定的或很少改变的。为了有效地完成这个任务，我应该使用哪一种算法？

这意味着在插入、更新或删除列表中的元素时应该做什么，从列表中获取前n个元素时应该做什么。

有一个解决办法(也许没那么好)：

1. 插入、更新或删除元素后，使用quicksort或其他排序算法对列表进行排序。，因为列表太大，这一步可能太慢了.
2. 获取前n个元素时，从列表中获取前n个元素。

有没有更好的解决办法？

Answer 1

因此，您有一个n项的列表，您希望选择最大的k。一种方法是使用大小为k的最小堆。得到的算法是O(n log )。

首先，创建第一个k项的空min堆。然后，对于列表中的每一项，如果它大于堆中最小的项，则移除堆中最小的项，并将其替换为新项。完成后，最大的k项将在堆中。伪代码如下所示：

// assume an array a[], with length n.
// k is the number of largest items you want.
heap = new min-heap

// add first k items to the heap
for (i = 0; i < k; ++i)
    heap.add(a[i])
for (i = k; i < n; ++i)
    if (a[i] > heap.peek())
        heap.removeMin()
        heap.add(a[i])
// at this point, the largest k items are on the min-heap

当k是n的一个很小的百分比时，这种方法工作得很好。在这种情况下，它只需要很少的内存。该算法在最坏的情况下运行时间为O(n log )，但高度依赖于列表中项的顺序。最坏的情况是数组按升序排序。最好的情况是数组按降序排序。在平均情况下，只有不到50%的项被添加并从堆中删除。

另一种算法快速选择的复杂度为O( n )，但当k是n的一个很小的百分比(1 %或2%)时，它比堆选择方法慢。Quickselect还修改现有的列表，这可能不是您想要的。

有关更多细节，请参阅我的博客文章https://blog.mischel.com/2011/10/25/when-theory-meets-practice/。

您可以在这里做一些事情，通过维护堆来加快平均时间，而不是为每个查询重新构建堆。

1. 如果您想要的项目数总是小于30项，那么始终保持一个由30个项组成的堆。如果用户只想要前10名，那么您可以从堆中只选择那些。
2. 当项被添加到列表中时，检查它是否大于堆中最小的项。如果是，请替换最小的项目。
3. 删除项时，将堆标记为脏。
4. 当被问到最上面的k项时，如果堆是脏的，那么您必须重新构建它。否则，您只需将堆的内容复制到一个划痕数组中，对其进行排序，并返回所要求的k项。当然，一旦您重新构建堆，清除脏标志。

因此，您可以以很少的代价维护堆:只要添加了一个新项，就有可能更新它，但前提是它大于前30项中的一个(或您的最大项)。您唯一需要重建的时间是删除后的顶部k项。

想想看，如果删除的项大于或等于堆中最小的项，则只需将堆标记为脏。另外，如果堆被标记为脏，那么您可以放弃对插入或删除的任何进一步更新，因为您必须在下次获得查询时重新构建堆。

Answer 2

一个(平衡的)二叉树是你最好的朋友。插入，删除，搜索k-所有在时间O(日志N).

如果数据驻留在外部内存中，则使用B树或类似的.

Answer 3

如果n <<<< size(list)使用哈希表作为主元素，使用配套的数据结构来存储n个最大的元素。辅助数据结构在插入和删除过程中进行更新，并用于查询最大的元素。如果n为30，则排序数组就足够了。

免责声明:如果最大的元素经常被删除，这种方法表现很差。删除最大的元素需要对整个哈希表进行顺序扫描。