ヒープデータ構造の実装

ヘッダファイル定義

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HeapValue;
typedef struct MinHeap {
    HeapValue* elements;
    int count;
    int capacity;
} MinHeap;

void HeapInitialize(MinHeap* heap);
void HeapDestroy(MinHeap* heap);
void HeapInsert(MinHeap* heap, HeapValue value);
void HeapRemoveRoot(MinHeap* heap);
HeapValue HeapGetTop(MinHeap* heap);
int HeapGetSize(MinHeap* heap);
bool HeapIsEmpty(MinHeap* heap);
void AdjustUpwards(HeapValue* array, int child_index);
void AdjustDownwards(HeapValue* array, int parent_index, int size);

実装コード

#include "heap_impl.h"

void HeapInitialize(MinHeap* heap) {
    assert(heap);
    heap->elements = NULL;
    heap->count = heap->capacity = 0;
}

void HeapDestroy(MinHeap* heap) {
    assert(heap);
    free(heap->elements);
    heap->elements = NULL;
    heap->capacity = heap->count = 0;
}

void ValueSwap(HeapValue* first, HeapValue* second) {
    HeapValue temp = *first;
    *first = *second;
    *second = temp;
}

void AdjustUpwards(HeapValue* array, int child_index) {
    assert(array);
    int parent_index = (child_index - 1) / 2;
    while (child_index > 0) {
        if (array[child_index] < array[parent_index]) {
            ValueSwap(&array[child_index], &array[parent_index]);
            child_index = parent_index;
            parent_index = (child_index - 1) / 2;
        } else {
            break;
        }
    }
}

void HeapInsert(MinHeap* heap, HeapValue value) {
    assert(heap);
    if (heap->count == heap->capacity) {
        int new_capacity = heap->capacity == 0 ? 4 : heap->capacity * 2;
        HeapValue* new_array = (HeapValue*)realloc(heap->elements, 
                                  sizeof(HeapValue) * new_capacity);
        if (new_array == NULL) {
            perror("Memory allocation failed");
            exit(EXIT_FAILURE);
        }
        heap->elements = new_array;
        heap->capacity = new_capacity;
    }
    heap->elements[heap->count] = value;
    heap->count++;
    AdjustUpwards(heap->elements, heap->count - 1);
}

void AdjustDownwards(HeapValue* array, int parent_index, int size) {
    assert(array);
    int child_index = parent_index * 2 + 1;
    while (child_index < size) {
        if (child_index + 1 < size && array[child_index] > array[child_index + 1]) {
            child_index++;
        }
        if (array[parent_index] > array[child_index]) {
            ValueSwap(&array[parent_index], &array[child_index]);
            parent_index = child_index;
            child_index = parent_index * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapRemoveRoot(MinHeap* heap) {
    assert(heap);
    assert(heap->count > 0);
    ValueSwap(&heap->elements[0], &heap->elements[heap->count - 1]);
    heap->count--;
    AdjustDownwards(heap->elements, 0, heap->count);
}

HeapValue HeapGetTop(MinHeap* heap) {
    assert(heap);
    assert(heap->count > 0);
    return heap->elements[0];
}

int HeapGetSize(MinHeap* heap) {
    return heap->count;
}

bool HeapIsEmpty(MinHeap* heap) {
    return heap->count == 0;
}

ヒープソートの実装

#include <stdio.h>
#include <assert.h>

void ElementSwap(int* elem1, int* elem2) {
    int temp = *elem1;
    *elem1 = *elem2;
    *elem2 = temp;
}

void SiftDown(int* array, int size, int index) {
    int child = index * 2 + 1;
    while (child < size) {
        if (child + 1 < size && array[child + 1] > array[child]) {
            child++;
        }
        if (array[child] > array[index]) {
            ElementSwap(&array[child], &array[index]);
            index = child;
            child = index * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSortArray(int* array, int length) {
    assert(array);
    for (int i = (length - 2) / 2; i >= 0; i--) {
        SiftDown(array, length, i);
    }
    
    for (int end = length - 1; end > 0; end--) {
        ElementSwap(&array[0], &array[end]);
        SiftDown(array, end, 0);
    }
}

二分木データ構造の実装

ノード構造と基本操作

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef char TreeNodeValue;
typedef struct BinaryTreeNode {
    TreeNodeValue data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} TreeNode;

TreeNode* TreeCreateFromPreorder(TreeNodeValue* sequence, int length, int* index);
void TreeDestroy(TreeNode** root);
int TreeCountNodes(TreeNode* root);
int TreeCountLeaves(TreeNode* root);
int TreeCountLevelNodes(TreeNode* root, int level);
TreeNode* TreeFindNode(TreeNode* root, TreeNodeValue target);
void TreePreorderTraversal(TreeNode* root);
void TreeInorderTraversal(TreeNode* root);
void TreePostorderTraversal(TreeNode* root);
void TreeLevelOrderTraversal(TreeNode* root);
int TreeIsComplete(TreeNode* root);

キュー実装（レベル順走査用）

#include "binary_tree.h"
#include <stdbool.h>

typedef TreeNode* QueueItem;
typedef struct QueueNode {
    struct QueueNode* next;
    QueueItem data;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
    int size;
} Queue;

void QueueInit(Queue* q);
void QueueEnqueue(Queue* q, QueueItem item);
void QueueDequeue(Queue* q);
QueueItem QueueFront(Queue* q);
int QueueSize(Queue* q);
bool QueueIsEmpty(Queue* q);
void QueueDestroy(Queue* q);

二分木操作の実装

#include "binary_tree.h"
#include "tree_queue.h"

TreeNode* CreateTreeNode(TreeNodeValue value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        perror("Node creation failed");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->left = node->right = NULL;
    return node;
}

TreeNode* TreeCreateFromPreorder(TreeNodeValue* sequence, int length, int* index) {
    if (*index >= length || sequence[*index] == '#') {
        (*index)++;
        return NULL;
    }
    
    TreeNode* node = CreateTreeNode(sequence[*index]);
    (*index)++;
    
    node->left = TreeCreateFromPreorder(sequence, length, index);
    node->right = TreeCreateFromPreorder(sequence, length, index);
    
    return node;
}

int TreeCountNodes(TreeNode* root) {
    if (root == NULL) return 0;
    return TreeCountNodes(root->left) + TreeCountNodes(root->right) + 1;
}

void TreeLevelOrderTraversal(TreeNode* root) {
    Queue q;
    QueueInit(&q);
    if (root != NULL) {
        QueueEnqueue(&q, root);
    }
    
    while (!QueueIsEmpty(&q)) {
        int level_size = QueueSize(&q);
        for (int i = 0; i < level_size; i++) {
            TreeNode* current = QueueFront(&q);
            QueueDequeue(&q);
            printf("%c ", current->data);
            
            if (current->left != NULL) QueueEnqueue(&q, current->left);
            if (current->right != NULL) QueueEnqueue(&q, current->right);
        }
        printf("\n");
    }
    QueueDestroy(&q);
}