データ構造 - ヒープ
ヒープ(Heap)は特殊な完全二分木構造であり、ヒープ順序の性質を満たします。ヒープは親子ノード間の大小関係のみを保証し、左右のサブツリー間に厳密な順序は要求しません。
ヒープの定義と格納
ヒープ (Heap) — 最大ヒープ構造と配列による格納
ツリービュー(最大ヒープ)
15インデックス0
10インデックス1
8インデックス2
53
34
25
配列ビュー(コンパクトな格納)
15
[0]10
[1]8
[2]5
[3]3
[4]2
[5]親:(i-1)/2 | 左の子:2i+1 | 右の子:2i+2
完全二分木 → 天然に配列に適しており、ポインタのオーバーヘッドがない
浮上 Sift Up(挿入)O(log n)
新しい要素を末尾に置く → 親と比較する → 大きければ交換する → ヒープの先頭まで繰り返す
沈下 Sift Down(ヒープ先頭の削除)O(log n)
末尾の要素をヒープ先頭に移動 → 大きい方の子と比較 → 小さければ交換 → 葉に到達するまで繰り返す
ヒープの2つのタイプ:
- 最大ヒープ(Max Heap):各親ノード ≥ 子ノード、ルートノードが最大値
- 最小ヒープ(Min Heap):各親ノード ≤ 子ノード、ルートノードが最小値
ヒープは完全二分木であるため、自然に配列での格納に適しています:
| ノード(インデックス i) | 関係 | 位置(0-based) |
|---|---|---|
| 親ノード | parent(i) | (i - 1) / 2 |
| 左の子ノード | left(i) | 2 * i + 1 |
| 右の子ノード | right(i) | 2 * i + 2 |
ヒープの挿入と削除(ヒープ化プロセス)
例
#include <stdio.h>
#define MAX 100
/* 最大ヒープ構造 */
struct MaxHeap {
int arr[MAX];
int size; /* 現在の要素数 */
};
void initHeap(struct MaxHeap* h) { h->size = 0; }
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* 浮上 (Sift Up):新しく挿入された要素を下から上へ調整
親ノードと比較し、親ノードより大きければ交換、ヒープ順序を満たすまで繰り返す */
void siftUp(struct MaxHeap* h, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (h->arr[idx] <= h->arr[parent]) break;
swap(&h->arr[idx], &h->arr[parent]);
idx = parent;
}
}
/* 挿入:まず要素を末尾に置き、浮上調整 O(log n) */
void insert(struct MaxHeap* h, int value) {
if (h->size >= MAX) return;
h->arr[h->size] = value;
siftUp(h, h->size);
h->size++;
}
/* 沈下 (Sift Down):ルートから下へ調整
大きい方の子ノードと比較し、小さければ交換、ヒープ順序を満たすまで繰り返す */
void siftDown(struct MaxHeap* h, int idx) {
while (1) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < h->size && h->arr[left] > h->arr[largest])
largest = left;
if (right < h->size && h->arr[right] > h->arr[largest])
largest = right;
if (largest == idx) break;
swap(&h->arr[idx], &h->arr[largest]);
idx = largest;
}
}
/* ヒープ先頭(最大値)の削除:末尾の要素を先頭に移動し、沈下調整 O(log n) */
int extractMax(struct MaxHeap* h) {
if (h->size == 0) return -1;
int maxVal = h->arr[0];
h->arr[0] = h->arr[--h->size]; /* 末尾の要素を先頭に移動 */
siftDown(h, 0); /* 沈下調整 */
return maxVal;
}
int main() {
struct MaxHeap h;
initHeap(&h);
int vals[] = {3, 10, 5, 8, 2, 15};
for (int i = 0; i < 6; i++) insert(&h, vals[i]);
printf("最大値を順に取り出し: ");
while (h.size > 0) {
printf("%d ", extractMax(&h));
}
printf("\n"); /* 出力: 15 10 8 5 3 2 (降順) */
return 0;
}
#define MAX 100
/* 最大ヒープ構造 */
struct MaxHeap {
int arr[MAX];
int size; /* 現在の要素数 */
};
void initHeap(struct MaxHeap* h) { h->size = 0; }
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* 浮上 (Sift Up):新しく挿入された要素を下から上へ調整
親ノードと比較し、親ノードより大きければ交換、ヒープ順序を満たすまで繰り返す */
void siftUp(struct MaxHeap* h, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (h->arr[idx] <= h->arr[parent]) break;
swap(&h->arr[idx], &h->arr[parent]);
idx = parent;
}
}
/* 挿入:まず要素を末尾に置き、浮上調整 O(log n) */
void insert(struct MaxHeap* h, int value) {
if (h->size >= MAX) return;
h->arr[h->size] = value;
siftUp(h, h->size);
h->size++;
}
/* 沈下 (Sift Down):ルートから下へ調整
大きい方の子ノードと比較し、小さければ交換、ヒープ順序を満たすまで繰り返す */
void siftDown(struct MaxHeap* h, int idx) {
while (1) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < h->size && h->arr[left] > h->arr[largest])
largest = left;
if (right < h->size && h->arr[right] > h->arr[largest])
largest = right;
if (largest == idx) break;
swap(&h->arr[idx], &h->arr[largest]);
idx = largest;
}
}
/* ヒープ先頭(最大値)の削除:末尾の要素を先頭に移動し、沈下調整 O(log n) */
int extractMax(struct MaxHeap* h) {
if (h->size == 0) return -1;
int maxVal = h->arr[0];
h->arr[0] = h->arr[--h->size]; /* 末尾の要素を先頭に移動 */
siftDown(h, 0); /* 沈下調整 */
return maxVal;
}
int main() {
struct MaxHeap h;
initHeap(&h);
int vals[] = {3, 10, 5, 8, 2, 15};
for (int i = 0; i < 6; i++) insert(&h, vals[i]);
printf("最大値を順に取り出し: ");
while (h.size > 0) {
printf("%d ", extractMax(&h));
}
printf("\n"); /* 出力: 15 10 8 5 3 2 (降順) */
return 0;
}
応用シーン
| シーン | 説明 |
|---|---|
| 優先度付きキュー | ヒープは優先度付きキューの最も一般的な基盤実装です |
| ヒープソート | O(n log n) のインプレースソートアルゴリズム(第18章で詳説) |
| Top K 問題 | 最小ヒープを使用して上位K個の最大要素を維持する |