1. ホーム
  2. data-structures

[解決済み] ヒープを使いたいのはどんなとき?

2022-11-10 05:05:08

質問

優先度キューという明白な答えの他に、ヒープが私のプログラミングの冒険で役に立つのはどんなときでしょうか?

どのように解決するのですか?

最大(または最小)の項目に素早くアクセスする必要があるときはいつでもこれを使用します。その項目は常に配列の最初の要素、またはツリーのルートになるからです。

しかし、配列の残りの部分は部分的にソートされていない状態で保持されます。そのため、最大(最小)項目に対してのみ即時アクセスが可能です。 挿入は高速なので、イベントやデータの着信に対応し、常に最も早い/最も大きいものにアクセスできる良い方法です。

優先キュー、スケジューラ(最も早いアイテムが望まれる場合)などに有用です...

ヒープとは、親ノードの値がその子孫ノードの値よりも大きいツリーのことです。

ヒープを、ルートノードが最初にあり(次にそのノードの子、その次にそれらのノードの子)、深さによる線形順序で格納された二分木と考えるなら、インデックスNのノードの子は2N+1および2N+2にあります。 この性質により、インデックス単位での素早いアクセスが可能となる。 また、ヒープはノードの入れ替えによって操作されるため、インプレースソートが可能になります。