配列を使用して要素を格納する MaxPQ ヒープがあります。ヒープ内の特定の要素を見つけるために使用できるアルゴリズムは何ですか? 私が現在使用しているアルゴリズムは、インデックス 1 から始まり、ヒープに追加された要素の数まで、配列を反復処理します。このアルゴリズムの複雑さは O(N) ですが、複雑さ O(logN) のアルゴリズムはありますか?
質問する
10145 次
1 に答える
8
ヒープ (最小または最大) を表す配列しかない場合、最悪の場合の対数アルゴリズムは見つからないのではないかと心配しています。一般的に検索するサブツリー。ルートが 100 で、その子が 90 と 80 で、5 を探している場合、(一般に) 両方のパスを探索する必要があります。
キーの配列内の位置を追跡する補助データ構造を保持している場合は、一定時間のルックアップをハックできます。http://eclipse.wells.edu/badams/courses/cs322/notes/topics/tools/heap.htmlで次の説明を見つけました
任意の要素を見つけるには、ノード名でインデックス付けされ、ヒープ内の位置 (ポインターまたはインデックス番号) でキー付けされた追加の配列を維持するのに役立ちます。これにより、任意のノードのルックアップが一定の時間で機能し、配列内のデータを維持するには、バブリング操作ごとに固定数のステップのみが必要になるため、ヒープアップまたはダウンの漸近時間を変更しません。
繰り返しになりますが、ヒープだけを考えると、最悪の場合は線形になりますが、実際には、ヒープをトラバースして剪定を行うと少しスピードアップする可能性があります。
于 2012-11-12T01:21:48.313 に答える