data-structures - いつヒープを使用する必要がありますか?

Question

プライオリティ キューの明白な答え以外に、プログラミングの冒険でヒープが役立つのはいつでしょうか?

Answer 1

最大（または最小）のアイテムにすばやくアクセスする必要がある場合はいつでも使用してください。そのアイテムは常に配列の最初の要素またはツリーのルートになるためです。

ただし、配列の残りの部分は部分的にソートされません。したがって、インスタントアクセスは最大（最小）のアイテムにのみ可能です。挿入は高速であるため、着信イベントまたはデータを処理するための優れた方法であり、常に最も早い/最も大きいものにアクセスできます。

優先キュー、スケジューラー（最も早いアイテムが必要な場合）などに役立ちます。

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

ヒープを、ルートノードを最初に（次にそのノードの子、次にそれらのノードの子）、深さごとに線形に格納されたバイナリツリーと考える場合。その場合、インデックスNのノードの子は2N+1と2N+2にあります。このプロパティにより、インデックスによる迅速なアクセスが可能になります。また、ヒープはノードを交換することで操作されるため、インプレースソートが可能になります。

Answer 2

ヒープの特徴は、データを半順序で維持する構造であるということです。したがって、完全な順序を維持するためのコストとランダムなカオスを検索するためのコストの間の適切なトレードオフです。この特性は、選択、順序付け、分類などの多くのアルゴリズムで使用されます。

ヒープのもう1つの便利な特性は、配列からインプレースで作成できることです。

Answer 3

選択アルゴリズムにも適しています（最小値または最大値を見つける）

Answer 4

一時リストをソートするときはいつでも、ヒープを考慮する必要があります。