ヒープ（データ構造） とは？

ソート済み配列は最大値の取得がO(1)だけど、挿入がO(n)かかる。ヒープは挿入も削除もO(log n)で、最大/最小値の取得がO(1)。データが動的に追加・削除される場面ではヒープの方が効率的。毎回ソートし直すよりずっと速いんだよ

通常のキューはFIFO（先入れ先出し）だけど、優先度付きキューは「優先度が高いものから出てくる」。ER（救急外来）の患者対応みたいなもので、到着順ではなく重症度順。内部実装にヒープを使うと、追加O(log n)・取り出しO(log n)・最高優先度の確認O(1)で効率的なんだよ

完全二分木は配列のインデックスで親子関係を表現できる。インデックスiのノードの左の子は2i+1、右の子は2i+2、親は(i-1)/2（切り捨て）。ポインタが不要でキャッシュ効率も良い。挿入は配列末尾に追加してから親と比較しながら上に移動（swim up）、削除はルートと末尾を入れ替えてから下に沈める（sink down）んだよ

Pythonのheapq、JavaのPriorityQueue、C++のpriority_queueがヒープの標準実装。①ダイクストラ法（最短経路）の「次に処理するノード」の管理、②ストリームデータからTop-K（上位K件）の取得、③タスクスケジューラの実装、④マージソートの外部ソート。競技プログラミングでは頻出だし、実務でもライブラリ経由でよく使っているんだよ