バイナリ最大ヒープを作成するとき、ツリー ベースではなく配列ベースとして実装する方がよいのはなぜですか (ツリー ベースのように、各ノードはその親へのポインターも持ちます)。ランタイム分析、メモリ使用量、パフォーマンスに関して...
バイナリ最大ヒープの場合、実行時間は次のとおりです。
- 挿入: O(lg n)
- 最小値を削除: O(lg n)
- マージ: O(n)
ツリー実装の場合
- 挿入: O(lg n)
- 最小値を削除: O(lg n)
- マージ: O(n)
誰か詳しく説明してくれませんか?
質問する
7750 次
2 に答える
14
ツリーはより多くの時間とメモリを使用します。複雑さは同じですが、定数要因が異なります。
ツリーのポインターは、配列ベースのヒープと比較して大量のメモリを使用します。配列ベースのヒープでは、追加のスペースはほとんど必要ありませんが、値自体が占有するスペースが必要です。また、これらのポインターの操作にも時間がかかります。ノードの割り当てと割り当て解除にも時間とスペースがかかる場合があります...
さらに、ツリーのノードがメモリ内で一緒になるという保証はありません。2 つの選択肢のいずれかがキャッシュを利用する場合、それは配列ベースのヒープです。
于 2013-02-06T09:11:57.603 に答える
6
他の人の回答ですでに述べられていることを参照すると、なぜ BST にも配列を使用しないのか不思議に思うかもしれません。バイナリ ヒープには、完全なバイナリ ツリーである必要があります。したがって、葉ノードの深さは常に h または h-1 です。配列の使用がバイナリ ヒープに理想的であり、BST には適さないのは、このプロパティだと思います (BST には完全なバイナリ ツリー要件がないため、厳密/完全/完全である可能性があります)。
于 2015-12-01T17:08:49.090 に答える