前書き

コンピュータサイエンスにおいて、ヒープ（Heap）は優先度付きキューの実装や効率的なソートアルゴリズム（ヒープソート）に使われる重要なデータ構造です。ヒープは完全二分木をベースにしており、配列による順序表現が可能で、メモリ効率と操作速度のバランスに優れています。

1. 木構造の基礎

1.1 木とは

木は非線形データ構造で、ノードの階層的集合です。根（ルート）ノードから始まり、子ノードへと枝分かれします。再帰的に定義され、任意のサブツリーもまた木です。

1.2 主な用語

• 次数（Degree）：ノードの子の数
• 葉ノード：子を持たないノード（次数0）
• 親・子・兄弟ノード：階層関係に基づく関係性
• 高さ（Height）：最も深いノードのレベル数
• 森（Forest）：互いに接続していない複数の木の集合

1.3 木の表現方法

代表的な表現法の一つが「左子右兄弟表現」です：

typedef struct TreeNode {
    struct TreeNode* firstChild;
    struct TreeNode* nextSibling;
    int data;
} TreeNode;

2. 二分木とその特性

2.1 二分木の定義

各ノードが最大2つの子（左・右）を持つ木。左右の順序が意味を持つ順序木です。

2.2 特殊な二分木

• 全二分木（Full Binary Tree）：すべてのノードが0または2個の子を持つ
• 完全二分木（Complete Binary Tree）：最後のレベル以外は完全に埋まっており、最後のレベルは左から詰まっている
• 満二分木（Perfect Binary Tree）：すべてのレベルが完全に埋まっている（ノード数 = \(2^h - 1\)）

2.3 二分木の性質

• 深さ \(h\) の二分木の最大ノード数は \(2^h - 1\)
• 葉ノード数 \(L\) と次数2のノード数 \(I\) の間には \(L = I + 1\) が成り立つ

2.4 格納方式

• 配列表現（順序構造）：完全二分木に適している。インデックス \(i\) のノードの
  • 親：\((i - 1) / 2\)
  • 左子：\(2i + 1\)
  • 右子：\(2i + 2\)
• ポインタ表現（リンク構造）：柔軟だがメモリオーバーヘッドあり

3. ヒープの概念

ヒープは完全二分木であり、以下の性質を持つ：

• 最小ヒープ：親 ≤ 子（根が最小値）
• 最大ヒープ：親 ≥ 子（根が最大値）

※ OSの「ヒープ領域」とは無関係です。

4. ヒープの実装

4.1 構造体とインターフェース

typedef int HPType;
typedef struct MinHeap {
    HPType* data;
    int size;
    int capacity;
} MinHeap;

void heap_init(MinHeap* h);
void heap_destroy(MinHeap* h);
void heap_push(MinHeap* h, HPType val);
void heap_pop(MinHeap* h);
HPType heap_top(const MinHeap* h);
bool heap_empty(const MinHeap* h);

4.2 初期化と解放

void heap_init(MinHeap* h) {
    h->data = NULL;
    h->size = h->capacity = 0;
}

void heap_destroy(MinHeap* h) {
    free(h->data);
    h->data = NULL;
    h->size = h->capacity = 0;
}

4.3 要素の挿入（Push）

static void swap(HPType* a, HPType* b) {
    HPType t = *a; *a = *b; *b = t;
}

static void adjust_up(HPType* arr, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (arr[idx] >= arr[parent]) break;
        swap(&arr[idx], &arr[parent]);
        idx = parent;
    }
}

void heap_push(MinHeap* h, HPType val) {
    if (h->size == h->capacity) {
        int new_cap = h->capacity ? h->capacity * 2 : 4;
        HPType* tmp = realloc(h->data, new_cap * sizeof(HPType));
        if (!tmp) return;
        h->data = tmp;
        h->capacity = new_cap;
    }
    h->data[h->size++] = val;
    adjust_up(h->data, h->size - 1);
}

4.4 要素の削除（Pop）

static void adjust_down(HPType* arr, int n, int idx) {
    int child = idx * 2 + 1;
    while (child < n) {
        if (child + 1 < n && arr[child + 1] < arr[child])
            child++;
        if (arr[idx] <= arr[child]) break;
        swap(&arr[idx], &arr[child]);
        idx = child;
        child = idx * 2 + 1;
    }
}

void heap_pop(MinHeap* h) {
    if (heap_empty(h)) return;
    h->data[0] = h->data[--h->size];
    adjust_down(h->data, h->size, 0);
}

4.5 その他ユーティリティ

HPType heap_top(const MinHeap* h) {
    return h->data[0];
}

bool heap_empty(const MinHeap* h) {
    return h->size == 0;
}

5. ヒープソート

最小ヒープを使って降順ソート（または最大ヒープで昇順）を実現できます：

void heap_sort(int* arr, int n) {
    // 最小ヒープ構築（ボトムアップ）
    for (int i = (n - 2) / 2; i >= 0; i--)
        adjust_down(arr, n, i);
    
    // ソート：最大値を末尾に移動
    for (int end = n - 1; end > 0; end--) {
        swap(&arr[0], &arr[end]);
        adjust_down(arr, end, 0);
    }
}

※ 上記は最小ヒープによる降順ソート。昇順なら最大ヒープを使うか、比較条件を逆にする必要があります。

6. Top-K 問題への応用

大量データの中から上位 K 個の要素を効率的に取得する問題。K 要素の最小ヒープを使います：

void find_top_k(const char* filename, int k) {
    FILE* fp = fopen(filename, "r");
    if (!fp) return;

    int* heap = malloc(k * sizeof(int));
    for (int i = 0; i < k; i++)
        fscanf(fp, "%d", &heap[i]);

    // K要素で最小ヒープ構築
    for (int i = (k - 2) / 2; i >= 0; i--)
        adjust_down(heap, k, i);

    int val;
    while (fscanf(fp, "%d", &val) == 1) {
        if (val > heap[0]) {
            heap[0] = val;
            adjust_down(heap, k, 0);
        }
    }

    // 結果出力（ヒープ内はTop-Kだが順不同）
    for (int i = 0; i < k; i++)
        printf("%d ", heap[i]);
    printf("\n");

    free(heap);
    fclose(fp);
}

この方法の時間計算量は \(O(N \log K)\)、空間計算量は \(O(K)\) で、大規模データに非常に有効です。