C言語による優先待ち行列の実装解説：ヒープを利用した効率的なデータ構造

#include <stdio.h>
#include <stdlib.h>
#define INITIAL_CAPACITY 10
// ヒープ構造体の定義
typedef struct {
    int *array;      // 要素を格納する配列
    int size;        // 現在の要素数
    int capacity;    // 配列の容量
} Heap;
// ヘルパー関数: 2つの値を交換する
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// ヒープの初期化を行う関数
void heapInit(Heap *heap, int capacity) {
    heap->array = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
}
// ヒープの領域を拡張する関数
void resizeHeap(Heap *heap) {
    heap->capacity *= 2;
    heap->array = (int*)realloc(heap->array, sizeof(int) * heap->capacity);
}
// 新しい要素をヒープに挿入する関数(最小ヒープを仮定)
void insertNode(Heap *heap, int value) {
    // 容量不足の場合は領域を拡張
    if (heap->size >= heap->capacity) {
        resizeHeap(heap);
    }
    // 新規要素を追加
    int index = heap->size;
    heap->array[index] = value;
    heap->size++;
    // バブルアップ操作
    while (index != 0) {
        int parent = (index - 1) / 2;
        // 親ノードの値より小さい場合に入れ替え
        if (heap->array[index] < heap->array[parent]) {
            swap(&heap->array[index], &heap->array[parent]);
            index = parent;
        } else {
            break;
        }
    }
}
// ルートの要素を削除し、ヒープを再構築する関数(最小ヒープを仮定)
int deleteNode(Heap *heap) {
    if (heap->size == 0) {
        return -1; // ヒープが空の場合のエラー値
    }
    int rootValue = heap->array[0];
    // 最後尾の要素をルートに移動
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // バブルダウン操作
    int index = 0;
    while (index < heap->size) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int smallest = index;
        // 左右の子と比較し、最小の要素を探索
        if (leftChild < heap->size && heap->array[leftChild] < heap->array[smallest]) {
            smallest = leftChild;
        }
        if (rightChild < heap->size && heap->array[rightChild] < heap->array[smallest]) {
            smallest = rightChild;
        }
        if (smallest != index) {
            swap(&heap->array[index], &heap->array[smallest]);
            index = smallest;
        } else {
            break;
        }
    }
    return rootValue;
}
// メイン関数: ヒープの動作確認用
int main() {
    Heap myHeap;
    heapInit(&myHeap, INITIAL_CAPACITY);
    // ヒープに値を挿入(例: 優先度の低い順に大きな値)
    insertNode(&myHeap, 20);  // "20"の優先度は低い
    insertNode(&myHeap, 15);
    insertNode(&myHeap, 30);
    insertNode(&myHeap, 10);  // "10"の優先度は高い
    // ヒープからルート要素を削除し、削除された要素を表示
    int minValue = deleteNode(&myHeap);
    printf("削除された要素: %d\n", minValue);
    // 残りのヒープ要素を順次削除し、表示する
    while (myHeap.size > 0) {
        printf("%d ", deleteNode(&myHeap));
    }
    printf("\n");
    // ヒープの動的確保した領域を解放
    free(myHeap.array);
    return 0;
}

削除された要素: 10
15 20 30