ヒープ / 優先度付きキュー（導入）

Heap（ヒープ）とはデータ構造の一種です。ヒープの実際の中身は ただの配列 となっています。また配列の中の要素には互いに大小関係があります。そして主に以下の3つの操作が登場します。(配列の要素数をNとしています。)

1. heapify: 事前に$\mathrm{O(N)}$の操作を行うことで、配列がヒープの構造となります。
2. heappush: ヒープの構造を保ちながら$\mathrm{O(logN)}$新しい値の追加を行います。
3. heappop: ヒープの構造を保ちながら$\mathrm{O(logN)}$最大値（最優先値）の取り出し（配列から削除）を行います。 またヒープの配列の先頭を参照することで最大値（最優先値）を$\mathrm{O(1)}$で知ることができます。

Priority Queue（優先度付きキュー）はある優先度（例として、大きい値を最優先する）に従って、 優先度の高いものから順に取り出すことの出来る集合を指します。 挿入順序がどうであれ、優先度の高いものが必ず1番最初に取り出されます。この優先度付きキューを実現するデータ構造としてヒープが使用されます。実際にはヒープ = 優先度付きキューとして考えてもほぼ問題ありません。