5

一定時間内にヒープ内の要素を見つけることができれば、ヒープの中央からノードを削除するのに O(lg n) を使用できます。ヒープのノードにフィールドとして id が含まれているとします。id を指定した場合、O(lg n) 時間でノードを削除するにはどうすればよいでしょうか?

解決策の 1 つは、ヒープ内のノードのインデックスを維持する、各ノード内の場所のアドレスを持つことができることです。この配列は、ノードIDによって注文されます。ただし、これには追加の配列を維持する必要があります。同じことを達成するための他の良い方法はありますか。

PS: Djikstra の Shortest Path アルゴリズムを実装しているときに、この問題に遭遇しました。

4

3 に答える 3

2

インデックス (id、ノード) は、O(1) ルックアップの複雑さ (平均) を持つハッシュテーブルで個別に維持できます。全体の複雑さは O(log n) のままです。

于 2012-09-26T17:55:32.167 に答える
0

各データ構造は、特定の操作を念頭に置いて設計されています。ヒープ操作に関するウィキペディアから

create-heap : 空のヒープ
を作成します。 find-max または find-min : max-heap の最大項目または min-heap の最小項目をそれぞれ検索します。delete
 -
 max または delete -min : 最大ヒープまたは最小ヒープのルート ノードをそれぞれ
削除し
ます。
ヒープを使用して、両方のすべての要素を含む有効な新しいヒープを形成します。

つまり、ヒープは、探している操作に最適なデータ構造ではありません。より適切なデータ構造を探すことをお勧めします（要件に応じて）。

于 2012-09-26T19:23:49.683 に答える