データ構造 - ヒープ

ヒープ(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;
}

応用シーン

シーン説明
優先度付きキューヒープは優先度付きキューの最も一般的な基盤実装です
ヒープソートO(n log n) のインプレースソートアルゴリズム(第18章で詳説)
Top K 問題最小ヒープを使用して上位K個の最大要素を維持する
その他の拡張