コレクション内の最小の要素を効率的に追跡するにはどうすればよいですか?

Question

その流れで プログラミングの質問:相互に比較して並べ替えることができるオブジェクトのコレクションがあるとします。オブジェクトが追加され、現在の最小要素が時々削除されるときに、コレクション内の最小要素を追跡する最も効率的な方法は何ですか?

Answer 1

最小ヒープを使用するのが最良の方法です。

http://en.wikipedia.org/wiki/Heap_(データ構造)

この用途に合わせて作られています。

Answer 2

ランダムな挿入と削除が必要な場合、最良の方法はおそらくソートされた配列です。挿入と削除は O(log(n)) である必要があります。

Answer 3

@ハープリート
それは最適ではありません。オブジェクトが削除されると、エリクソンはコレクション全体をスキャンして、新しい最小のものを見つける必要があります。

読みたいのは 二分探索木さんの。MSには良い点がある サイト 道を歩み始めるために。しかし、次のような本を手に入れたいかもしれません アルゴリズムの概要 (Cormen、Leiserson、Rivest、Stein) 深く潜りたい場合は。

Answer 4

時々削除します フィボナッチヒープ 最小ヒープよりもさらに高速です。挿入は O(1) で、最小値の検索も O(1) です。削除は O(log(n))

Answer 5

ランダムな挿入と取り外しが必要な場合、最良の方法はおそらくソートされた配列です。挿入と取り外しはo（log（n））でなければなりません。

はい、ただし、挿入ごと、および（おそらく）削除ごとに再ソートする必要があります。これは、前述のとおり、O(log(n)) です。

Harpreet が提案したソリューションでは次のようになります。

• 最小の要素を見つけるために最初に 1 つの O(n) パスがあります
• それ以降の挿入は O(1) です (既知の最小要素との比較は 1 回だけ必要です)
• 最小の要素を再検索する必要があるため、削除は O(n) になります (Big O 表記は最悪の場合であることに注意してください)。削除する要素が (既知の) 最小であるかどうかを確認して最適化することもできます。そうでない場合は、最小の要素を見つけるための再チェックを行わないでください。

したがって、それは状況によります。これらのアルゴリズムの 1 つは、削除がほとんどなく、挿入が多いユースケースに適していますが、もう 1 つは全体的により一貫性があります。最小の数値が頻繁に削除されることがわかっていない限り、私は Harpreet のメカニズムをデフォルトで使用すると思います。それはアルゴリズムの弱点を露呈するからです。

Answer 6

ハープレット:

挿入のために項目を移動する必要があるため、そこへの挿入は線形になります。

それはコレクションの実装に依存するのではないでしょうか？リンクされたリストのように動作する場合、挿入は O(1) になりますが、配列のように実装された場合は、述べたように線形になります。

Answer 7

コンテナでどの操作をサポートする必要があるかによって異なります。あ 最小ヒープ いくつかの操作は簡単ではありませんが (場合によっては償却 log(n) 時間)、任意の時点で min 要素を削除する必要がある場合に最適です。

ただし、前面/背面からのプッシュ/ポップのみが必要な場合は、すべての操作 (findmin を含む) で償却定数時間を実現する mindeque を使用するだけです。できるよ Scholar.google.com の検索 この構造について詳しく知るには、最近、友人と私は協力して、ミンデクのよりわかりやすく、実装しやすいバージョンを作成しました。これがあなたが探しているものであれば、詳細を投稿できます。