スタックとキューの記事の最後で予告したデータ構造シリーズ第2回です。今回の主役はヒープですが、その前に一つ誤解を解きます。
関連記事スタックとキュー完全ガイド：SwiftにStack型がない理由（removeFirstの罠まで）で、背景概念と応用例を確認できます。
**データ構造のヒープはメモリのヒープと名前が同じだけで、関係はありません。**メモリのヒープ領域は動的割り当て領域で、ここで扱うヒープは「最小値（または最大値）をO(1)で取り出す木」です。
メモリ割り当て領域の違いはスタック vs ヒープで分けて説明します。この記事ではデータ構造のHeapとPriority Queueに集中します。
スタック vs ヒープの記事でそのヒープを想像したなら、ここはまったく別の世界です。
ヒープが解決する問題は明確です。
「最も急ぎのものから処理したい。でも全体をソートしておくのはもったいない。」
ソートは過剰だ
最優先のタスクから取り出す待ち行列を作るとします。配列を毎回ソートすると、挿入のたびにO(n log n)です。
ソート済みを保って挿入位置を探しても、要素の移動でO(n)になります。
考えてみれば、必要なのは全体のソートではありません。今最も急ぎの一つがすぐ分かれば十分です。
2番目が誰かは、1番目がいなくなってから分かっても遅くありません。
ヒープが保証するのは、まさにこれだけです。だから挿入も削除もO(log n)で完了します。
「約束を減らすほど速くなる」は、データ構造設計の代表的なトレードオフです。
ヒープの規則：親は子より小さい。それだけ
最小ヒープは完全二分木で、規則は一つだけです。
すべての親は、自分の子以下です。
兄弟同士の大小は問いません。左部分木が右より小さい必要もありません。
親子関係だけ守ればよいのです。この緩さにより、根には常に全体の最小値がありますが、それ以上は保証しません。
挿入（sift up）：木の末尾に追加し、親より小さければ交換して上へ移動します。木の高さ分しか動かないためO(log n)です。
最小値の取り出し（sift down）：根を外し、末尾要素を根へ移して、二つの子の小さい方と交換しながら下げます。同じくO(log n)です。
配列で木を作る魔法
ヒープの実装が美しいのはここです。完全二分木は空きを作らず左から埋まるため、ポインタなしで配列に順番に置けます。（NIST Heap）。
インデックス: 0 1 2 3 4 5
値: [1, 3, 2, 7, 4, 5]添字計算だけで親子関係が分かります。
- 親：
(i - 1) / 2 - 左の子：
2i + 1、右の子：2i + 2
ノードオブジェクトも子ポインタもヒープメモリ割り当てもありません。配列 vs 連結リストで扱うキャッシュ局所性の利点を得ながら、木の論理構造だけを借りています。
Swiftで骨格を書くと次のようになります。
struct MinHeap<Element: Comparable> {
private var elements: [Element] = []
var min: Element? { elements.first } // O(1)
mutating func insert(_ value: Element) { // O(log n)
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func removeMin() -> Element? { // O(log n)
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let min = elements.removeLast()
siftDown(from: 0)
return min
}
}siftUp/siftDownは、上で説明した交換の反復です。
なお、既存配列全体をヒープにするbuild-heapは、要素ごとに挿入するO(n log n)ではありません。下半分からsift downすれば**O(n)**で完了します。面接でよく問われる細部です。
実務でのヒープの立ち位置
**優先度キューはヒープそのものです。**スタック・キューの記事の表現なら、キューは到着順、優先度キューは緊急度順に取り出す待ち行列で、その標準実装がヒープです（NIST Priority Queue）。
- OSスケジューラ：優先度の高いプロセスからCPUを割り当てる
- ダイクストラ最短経路：「これまでに見つかった経路で最短のもの」を繰り返し取り出すアルゴリズム。ヒープがなければ性能が崩れます
- タイマー管理：多数のタイマーのうち、最初に鳴るものだけ分かればよいシステム内部構造
- ヒープソート：すべて入れてすべて出せばO(n log n)のソートになります。追加メモリなしでその場ソートできるのが強みです
- Top-K問題：「ストリームから最大のK個を維持する」問題。サイズKの最小ヒープでO(n log K)に解ける、コーディングテスト定番のパターンです
Swift標準ライブラリにヒープはありません。スタック・キュー記事のDequeと同様、Appleのswift-collectionsパッケージがHeapを提供します（swift-collections Heap）。
minとmaxの両方をO(log n)で扱うmin-max heap実装です。コーディングテストのように外部パッケージを使えない環境では、上のMinHeapの骨格を身につけておくのが実践的です。
まとめ
- データ構造のヒープはメモリのヒープと名前が同じだけで、「最小値を即座に取り出す木」です
- 規則は親≤子だけ。全体のソートを諦める代わりに、挿入・削除はO(log n)です
- 完全二分木なので配列にポインタなしで置けます。親は
(i-1)/2、子は2i+1、2i+2 - 優先度キューの標準実装がヒープで、ダイクストラ、スケジューラ、Top-Kが代表的な用途です
- Swiftではswift-collectionsの
Heap、コーディングテストでは自前実装が定石です
次回はハッシュテーブルです。Swift DictionaryがどのようにO(1)を実現するのか、Hashableが要求することの本当の意味を扱います。
出典と確認基準
- swift-collections HeapApple · 公式ドキュメント · 確認日 2026年8月17日根拠: Swift Heap APIと最小・最大ヒープの動作
- NIST Dictionary of Algorithms: Priority QueueNIST · 公式データ · 確認日 2026年8月17日根拠: 優先度キューの抽象データ型の定義
- NIST Dictionary of Algorithms: HeapNIST · 公式データ · 確認日 2026年8月17日根拠: 配列ベースのヒープの構造と演算特性