最大ヒープと優先度キュー：実装とアプリケーション
最大ヒープがルートに最大要素を維持する方法と、優先度キューの実装方法を学びます。最小ヒープと比較し、スケジューリングやTop-K問題でのアプリケーションを探索します。
Heap
詳細な説明
最大ヒープと優先度キュー
最大ヒープはすべての親が子以上である完全二分木です。最大要素は常にルートにあります。
最大ヒープ特性
9
/ \
7 8
/ \ / \
3 5 6 2
すべての親 ≥ 両方の子。配列：[9, 7, 8, 3, 5, 6, 2]
優先度キュー
優先度キューは各要素に優先度がある抽象データ型です。最高優先度の要素が挿入順に関係なく最初に処理されます。ヒープが標準的な実装です。
Top-K問題
最大ヒープと最小ヒープはTop-K問題によく使用されます：
- K個の最大要素：サイズKの最小ヒープを使用。各新しい要素について、ヒープの最小値より大きければ最小値を抽出して新しい要素を挿入。
- K個の最小要素：サイズKの最大ヒープを使用。ミラーロジック。
このアプローチはO(n log K)であり、Kがnよりはるかに小さい場合、ソートのO(n log n)より優れています。
ユースケース
ヒープで実装された優先度キューはタスクスケジューラ、ネットワークルーター、A*パスファインディング、2つのヒープによる中央値検出に使用されます。Top-Kパターンはコーディング面接や実世界のデータ処理で頻繁に登場します。