アレイを使用したバイナリツリーの表現

Question

古いノードベースの実装ではなく、バイナリツリーの配列ベースの実装を使用すると、速度/空間/一般的なパフォーマンスが向上しますか？私は回転や配列ベースのツリーの他の複雑な変更は恐ろしいだろうが、単純なバイナリツリー実装の場合は、配列を使って行うほうが良いと言いますか？

Answer 1

私はあなたがBinary Heapを探していると思います。

Answer 2

アレイベースのバージョンではヒープ割り当ては使用されないため、キャッシュに収まる可能性が高く、トラバースに必要な読み込み速度を上げるためにポインタの計算が簡単になります。コンパイル時にサイズが制限されている場合は、より高速な解決方法です。