ヒープ（二分ヒープ）
最終更新
二分ヒープは、最小値（最小ヒープ）または最大値（最大ヒープ）を根に保つ完全二分木です。この可視化は最小ヒープで、すべての親はその子以下です。値を追加するには次の空いている位置に付け足し、その後、親より小さい間は親と交換して「上へふるい上げ」、ヒープ条件が再び満たされるまで続けます。上の再生ボタンを押して、各新しい値が自分の位置まで浮上する様子を見てください。
ヒープは完全木なので配列にコンパクトに格納されます。ノード i の子は 2i+1 と 2i+2 にあります。挿入と最小値の削除は O(log n)（根から葉までの1つの経路）で、最小値の参照は O(1) です。これはまさに優先度付きキューが必要とするものです。
時間計算量と空間計算量
| 操作 | 計算量 | 備考 |
|---|---|---|
| 最小/最大の参照 | O(1) | 常に根にある |
| 挿入（push） | O(log n) | 1つの経路を上へふるい上げ |
| 最小/最大の削除 | O(log n) | 1つの経路を下へふるい下げ |
| ヒープの構築 | O(n) | 一度にheapify |
| 空間 | O(n) | 配列ベース、ポインタなし |
ステップごと（push）
| ステップ | 何が起こるか |
|---|---|
| 1 | 新しい値を末尾（次の空いている葉）に付け足す。 |
| 2 | それを親と比較する。 |
| 3 | 小さければ（最小ヒープ）、上へ交換する。 |
| 4 | 親より小さくなくなるか、根に達するまで繰り返す。 |
実例
[5, 3, 8, 1, 4] を1つずつ挿入して最小ヒープを構築する：
| Push | ふるい上げ後の配列 | 動作 |
|---|---|---|
5 | [5] | 最初の値が根になる。 |
3 | [3, 5] | 3 < 親 5 なので、根まで上がる。 |
8 | [3, 5, 8] | 8 > 親 5 なので、葉のままとどまる。 |
1 | [1, 3, 8, 5] | 1 < 親 5 で交換、次に 1 < 親 3 で根まで上がる。 |
4 | [1, 3, 8, 5, 4] | 4 > 親 3 なのでとどまる。最小値 1 は根に残る。 |
ヒープを使うべき場面
| 使うべき場面 | 避けるべき場面 |
|---|---|
| 変化する集合から最小または最大の要素を繰り返し必要とするとき。 | 極値だけでなく任意の値を検索する必要があるとき - BSTやハッシュ集合を使う。 |
| Dijkstra、A*、スケジューラ向けに優先度付きキューを実装するとき。 | データを常に完全にソートされた状態で保つ必要があるとき。 |
コンパクトな配列レイアウトで O(log n) の挿入と最小値削除が欲しいとき。 | 特定の（根でない）要素の高速な検索や削除が必要なとき。 |
| 要素のストリームをマージし、優先度順に取り出す必要があるとき。 | データ集合がごく小さく、線形走査の方が単純で十分速いとき。 |
Heap (Priority Queue)のコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なHeap (Priority Queue)の実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのHeap (Priority Queue)のコード
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])JavaScriptでのHeap (Priority Queue)のコード
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));JavaでのHeap (Priority Queue)のコード
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}C++でのHeap (Priority Queue)のコード
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}CでのHeap (Priority Queue)のコード
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}ヒープに関するよくある質問
ヒープは何に使われますか？
ヒープは優先度付きキューを実装し、Dijkstraの最短経路アルゴリズム、タスクスケジューラ、イベントシミュレーションを支えます。ヒープソートの原動力でもあります。変化する集合から最小または最大の要素を繰り返し必要とするときはいつでも、ヒープが適した道具です。
ヒープと二分探索木の違いは何ですか？
どちらも二分木ですが、BSTは左から右への完全な整列順序を保ち（順序付き探索を可能にし）、一方ヒープは親子関係だけ（根に最小または最大）を保証します。ヒープは極値へのO(1)アクセスを与え、BSTは任意の値へのO(log n)探索を与えます。
なぜヒープは配列に格納されるのですか？
ヒープは常に完全二分木なので、そのノードは配列のインデックスに完全に対応します。インデックス
i の子は 2i+1 と 2i+2 にあり、親は (i-1)/2 にあります。これにより子へのポインタを格納せずに済み、優れたキャッシュ性能が得られます。ヒープはソート済み配列と同じですか？
いいえ。ヒープは各親が子より小さい（最小ヒープ）または大きい（最大ヒープ）ことだけを保証するので、兄弟やいとこには特定の順序がありません。ソート済み配列は完全に整列していますが挿入に
O(n) かかり、一方ヒープは O(log n) で挿入でき、それでも極値への即時アクセスを与えます。配列を単にソートする代わりに、いつヒープを使うべきですか？
データが変化し続け、現在の最小値または最大値だけが必要なときはヒープを使いましょう。挿入と取り出しはそれぞれ
O(log n) で、配列全体を再ソートするより有利です。静的なデータ集合で全要素を順に欲しいなら、1回の O(n log n) ソートの方が単純で多くの場合速いです。n個の要素からヒープを構築するのに O(n log n) かかりますか？
一度に構築すればかかりません。
n 個の要素を1つずつ挿入すると O(n log n) ですが、最後の親から根へ向かってふるい下げるボトムアップの heapify は全体で O(n) で動きます。ほとんどのノードは底に近く、短い距離しかふるい下げないからです。関連リソース
その他の可視化
