順序付きリンクリストのセットの並べ替え

Question

次の問題に対するエレガントで高性能なソリューションを探しています。

256個のリンクリストがあります。

• 各リストには、ソート順を定義するために使用される整数を保持するオブジェクトと同じタイプのオブジェクトが含まれています。
• すべてのリストのすべての数字は一意です
• 各リストは、これらの番号で昇順にソートされます

元の256個のリンクリストのすべてのオブジェクトから単一の昇順リストを作成するにはどうすればよいですか？私はそれをブルートフォースしたり、他のいくつかのアイデアを持ちたくないのですが、これは標準的な最適なソリューションがある問題の1つのようです。

Answer 1

＆＃8220;最上位＆＃8221;を保持する優先度キューを使用できます256個のリンクリストのそれぞれの項目。これ＆＃8220; topmost＆＃8221; itemは、結果リストに挿入される予定のアイテムです。このようにして、優先度キューから最小の要素を取り出して、結果のキューに挿入し、次の要素を優先度キューに挿入することができます。

# Preprocessing:
result = list.new()
queue = priority_queue.new()

foreach (list in lists):
    queue.push(list.first())

# Main loop:
while (not queue.empty()):
    node = queue.pop()
    result.insert(node)
    if (node.next() != null):
        queue.push(node.next())

Answer 2

個々のリストが既にソートされている場合、それはマージアルゴリズムの直接適用です。要するに、すべてのヘッドを比較して最小のものを選択し、リストから取り出して出力リストにプッシュします。すべてのソースリストが空になるまで繰り返します。

編集：Konradによる優先度キューの使用（ヒープ）ははるかにエレガントでスケーラブルなソリューションですが、おそらく256の入力リストが非常に少ないため、単純な比較の方が高速になる可能性があります。

Answer 3

各リストをその上のリスト128にマージするだけです。 （128個のリストになります）
次に、各リストをその上のリスト64にマージします。 （結果は64個のリストになります）
次に、各リストをその上のリスト32とマージします。 （結果は32リスト）
次に、各リストをその上のリスト16にマージします。 （16個のリストになります）
次に、各リストをその上のリスト8とマージします。 （結果は8つのリストになります）
次に、各リストをその上のリスト4とマージします。 （4つのリストになります）
次に、各リストをその上のリスト2とマージします。 （2つのリストになります）
次に、各リストをその上のリスト1とマージします。 （1つのリストになります）
（上記にはループを使用できます）。

Answer 4

これらのリストの長さについては言及していませんが、すべてが同時にRAMに収まると仮定しています。私が最初に試みることは、それらをすべて一緒に追加し、私の環境の組み込みソートルーチンを呼び出すことです。実装は簡単で、テストに時間がかかりません。許容できるパフォーマンスが得られない場合は、Konrad Rudolphが提供する優先キューマージを使用します。