私はこの問題を抱えています -同じデータを含まない最小ヒープと最大ヒープの 2 つの異なるヒープを含むデータ構造を保持しています。
私の目標は、ヒープのいずれかで各ノードの場所についてある種の記録を保持し、ヒープ アクションで更新することです。結論 - lg(n) の複雑さで機能する delete(p) 関数をどのように使用できるかを理解しようとしています。p は、任意のデータを保持できるポインタ データ オブジェクトです。
ありがとう、ネッド。
質問する
200 次
1 に答える
1
ヒープがアイテムの配列（参照など）として実装されている場合、O（n）時間でヒープ内の任意のアイテムを簡単に見つけることができます。そして、アイテムがヒープ内のどこにあるかがわかれば、O（log n）時間でそれを削除できます。したがって、検索と削除はO（n + log n）です。
この回答で説明しているように、ヒープを辞書またはハッシュマップとペアリングすると、削除のためにO（log n）を達成できます。
ここでは、O（log n）時間で任意の項目を削除する方法について説明します。
ディクショナリアプローチの秘訣は、ディクショナリにキー（アイテムキー）と、ヒープ内のノードの位置である値が含まれていることです。ヒープ内のノードを移動するたびに、ディクショナリ内のその値を更新します。この場合、log（n）辞書の更新を行う必要があるため、挿入と削除は少し遅くなります。ただし、これらの更新はO（1）であるため、それほど高価ではありません。
または、ヒープがバイナリツリーとして実装されている場合（配列内の暗黙的な構造ではなく、ポインターを使用）、ノードへのポインターをディクショナリに格納でき、挿入または削除するときにノードを更新する必要はありません。ヒープ。
そうは言っても、ペアのデータ構造での最小の追加と削除（または最大ヒープの場合は最大の削除）の実際のパフォーマンスは、任意の削除を多数実行しない限り、配列として実装されている標準のヒープよりも低くなります。 。たまに任意のアイテムを削除するだけの場合、特にヒープがかなり小さい場合は、O（n）削除のパフォーマンスを使用したほうがよいでしょう。実装は簡単で、nが小さい場合、O（n）とO（log n）の間に実際の違いはほとんどありません。
于 2013-03-13T21:27:30.767 に答える