如何有效地找到列表中的n个最小元素？

Question

查找list<float>中的n个最小元素可以通过对列表进行排序并选择n个最小元素来完成。但是，使用堆也可以更有效地完成此任务。我发现了几个用于F#的堆的实现，但没有示例说明如何将它们用于此目的。我的两个绊脚石是：

1)我找不到从列表创建堆的方法。我所见过的所有实现都提供了一种创建空堆并具有insert方法的方法。我应该创建一个空的堆并一个接一个地插入项吗？这看起来很慢，这将违背其目的。

2)没有一个实现有像这样的nLargest或nSmallest方法，例如，Python代码：

from heapq import nlargest
lst = [9,1,6,4,2,8,3,7,5]
nlargest(3, lst) # Gives [9,8,7]

有没有简单的方法来解决这个问题？

Answer 1

请注意，您实际上并不需要为此使用堆。例如，关于如何实现快速排序以在不预先执行所有工作的情况下生成排序序列的信息，请参见Jon Skeet's old post。(不幸的是，这篇文章中有一些不相关的论述，因为它只是重新实现LINQ-to-objects的长篇系列文章的一部分)

Answer 2

如何将数组重新排列为二进制堆：

从数组的中间开始向后移动，向下筛选堆中的每个元素。例如，假设您有一个长度为n的数组a。下面的代码将完成此操作：

for i = n/2 downto 0
    siftDown(i);

和siftDown方法：

siftDown(int index)
{
    while (index < n/2)
    {
        // find the smallest child
        int ixChild = (ix * 2) + 1;
        if (ixChild < n-1 && a[ixChild] > n[ixChild + 1])
        {
            ixChild = ixChild + 1;
        }
        // if the item is <= the smallest child, we're done
        if (a[i] < a[ixChild]) break;

        // otherwise, swap with the smallest child
        swap(i, ixChild);

        // and do it again
        i = ixChild;
    }
}            

在列表中选择k最小项的另一种方法是使用Quickselect，这基本上是一种快速排序分区方法。这样做的优点是O(n)，这通常比使用堆更快。当算法完成时，k中最小的项位于数组的前面，但它们没有排序。

最后，如果希望使用堆选择方法，可以考虑使用Pairing heap而不是二进制堆。配对堆有O(1)个插入和O(log )个删除。此外，从维基百科页面上的示例可以很容易地在F#中实现它。