data-structures - プライオリティ キューを表すのにヒープがバイナリ ツリーより優れているのはなぜですか?

Question

(最大) ヒープでは、O(1)時間内に最大のアイテムを見つけるのは簡単ですが、実際にそれを削除するには、 の複雑さが必要ですO(log(n))。

では、ヒープへの挿入と削除の両方O(log(n))が .

Answer 1

1. ヒープはより少ないメモリを使用します。それらは配列として実装できるため、ポインターを格納するためのオーバーヘッドはありません。(バイナリ ツリーは配列として実装できますが、多くの空の「ギャップ」が存在する可能性があり、ポインターを使用してノードとして実装するよりも多くのスペースを浪費する可能性があります)。

2. ヒープは、ノードの値がその子の値を支配するだけで、要素が順序通りのトラバーサルによってソートされた順序で取得できることを保証する必要がないため、log(n) の高さを持つことが保証されます。これにより、「パックされた」構造を配列として持つことができます。二分木 (バランスのとれた二分木でない限り) は、通常、log(n) よりも大きな高さの枝を持つことになるため、操作の複雑さが同じでも、実際のヒープはわずかに高速になります。

3. ヒープは配列として実装できるため、メモリがあちこちに散らばっているポインタが指すノードにアクセスするよりも、まだキャッシュ内にある可能性が高い連続したメモリにアクセスできるという大きな利点があります。

4. ヒープはバイナリ ツリーよりも実装が簡単です (特にバランスの取れたバイナリ ツリー)。

欠点は、ヒープではバイナリ検索を実行できないことですが、プライオリティ キューではこの機能は必要ありません。