algorithm - ヒープを使用した外部ソート?

Question

大量のデータを含むファイルがあり、特定の時点でデータの一部のみをメモリに保持してソートしたいと考えています。

マージソートは外部ソートで人気があることに気付きましたが、ヒープ (最小または最大) で実行できるかどうか疑問に思っています。基本的に私の目標は、メモリ内に 10 個を超えるアイテムを保持することなく、100 個のアイテム リストで (任意の数を使用して) 上位 10 個のアイテムを取得することです。

私はほとんどヒープを理解しており、データをヒープ化すると適切な順序になることを理解しています。そこから、ソリューションとして最後の部分を取り出すことができますが、I / Oなしで行う方法がわかりませんすべての気紛れなアイテムのために。

アイデア？

ありがとう！:D

Answer 1

ヒープには、多くの非順次アクセスが必要です。Mergesort は、大量のシーケンシャル アクセスを行うため、外部ソートに最適です。

シーケンシャル アクセスは、ヘッドが移動する必要がないため、回転する種類のディスクでは非常に高速です。シーケンシャル アクセスは、おそらくファイル内の単一のものよりもかなり大きいブロックでアクセスを行うため、ヒープソートのアクセスよりもソリッド ステート ディスク上ではるかに高速になるでしょう。

Answer 2

Merge sortを使用して 2 つの値を参照渡しすることにより、2 つの比較値をバッファーに保持し、適切な場所に並べ替えられるまで配列全体を移動するだけで済みます。