ヒープ（優先度キュー）パターン

中級

カテゴリ: queues

概要

ヒープは特殊な二分木ベースのデータ構造で、最大値または最小値への効率的なアクセスを提供します。最大ヒープでは親ノードが常に子ノードより大きく、最小ヒープでは親ノードが常に子ノードより小さくなります。優先度キューはヒープを使って実装されることが多く、要素を優先度順に処理できます。要素の追加と最大/最小要素の取り出しが O(log n) で行えるため、「上位k個の要素」や「k番目に大きい/小さい要素」を見つける問題に特に有効です。

コードテンプレート

Java

Python

- 優先度キュー（最小ヒープ）
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // デフォルトは最小ヒープ
minHeap.offer(3); // 要素の追加
minHeap.offer(1);
minHeap.offer(2);
int min = minHeap.peek(); // 最小値の参照（1）
int removed = minHeap.poll(); // 最小値の取り出しと削除（1）

// Java - 優先度キュー（最大ヒープ）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
int max = maxHeap.peek(); // 最大値の参照（3）

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

優先度キュー最大ヒープ最小ヒープ上位k個k番目に大きいk番目に小さい優先度順処理動的な最大/最小値中央値の維持ヒープソート完全二分木ダイクストラアルゴリズムプリムアルゴリズムマージソート済みストリーム効率的な挿入と削除

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
k番目に大きい要素（Kth Largest Element）: 配列内のk番目に大きい要素を見つける
2
最も近いk個の点（K Closest Points to Origin）: 原点に最も近いk個の点を見つける
3
合併されたk個のソート済みリスト（Merge k Sorted Lists）: k個のソート済みリストを1つのソート済みリストに統合する
4
データストリームの中央値（Median of Data Stream）: 動的に変化するデータストリームの中央値を常に取得できるようにする

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

中

頻出上位K要素

整数の配列 nums と整数 k が与えられたとき、配列内で最も頻繁に出現する k 個の要素を返してください。任意の順序で返すことができます。...

中

配列内のK番目に大きい要素

整数の配列 nums と整数 k が与えられたとき、配列内のk番目に大きい要素を見つけて返してください。 k番目に大きい要素とは、配列をソートした後にインデックス n-k の位置にある要素のことです...

難

データストリームの中央値

データストリームから中央値を見つけるためのデータ構造を設計してください。中央値とは、ソートされたデータセットの中央に位置する値です。データの数が奇数の場合、中央値は中央の要素です。データの数が偶数...