arrays - リンク リストを使用したバイナリ ヒープの複雑さ

Question

配列とリンクリストを使用してバイナリヒープの実装を比較しようとしています。すべての操作が連結リストを使用した操作と同等かそれ以上に高速に実行できるため、あらゆる点で配列の方が優れていると思います。また、必要なメモリも少なくなります。

しかし、リンクされたリストを使用する方がバイナリ ヒープの配列よりも優れている理由はありますか?

Answer 1

バイナリ ヒープが明示的なツリーとして表されることはめったにありません。それらは配列バージョンよりも多くのメモリを使用し、参照の局所性が低く、(以前の質問で指摘したように) 実装が困難です。

バイナリ ヒープをツリーとして研究する主な理由は、データ構造の直感を構築することです。配列表現だけが与えられた場合、バイナリ ヒープのプロパティと正確性について推論することは非常に困難ですが、それらをバイナリ ツリー表現に接続することで、バイナリ ヒープのアルゴリズムの設計と正確性を証明することがはるかに簡単になります。

お役に立てれば！