リスト内のn個の最小要素を効率的に見つける方法を教えてください。

Question

list<float>でn個の最小要素を見つけるには、リストをソートしてn個の最小要素を選択します。しかし、ヒープを使ってより効率的に行うこともできます。私はF＃のヒープのいくつかの実装を見つけましたが、この目的のためにそれらを使用する方法の例はありませんでした。私の2つの障害は次のとおりです。

1）リストからヒープを作成する方法が見つかりませんでした。私が見たすべての実装は、空のヒープを作成する方法を提供し、insertメソッドを持っています。空のヒープを作成し、アイテムを1つずつ挿入する必要がありますか？それは遅く見えますが、それは目的を破るでしょう。

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

：

アレイの中央から開始し、後方に移動するが、ダウンヒープ内の各要素をふるいにかけます。たとえば、配列がaで、長さがnであるとします。以下はそれを行います。

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 n）除去があります。さらに、Wikipediaの例のF＃で実装するのはかなり簡単です。

Answer 2

これにはヒープを使用する必要はありません。たとえば、Jon Skeet's old postを参照してください。クイックソートを実装して、すべての作業を前もって実行せずにソートされたシーケンスを生成します。 （残念なことに、LINQからオブジェクトへの再実装の長いシリーズの一部に過ぎないので、ポストには関連のない説明があります）