min_heap.c

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    int capacity;
    int size;
} BinaryHeap;

// Function prototypes
BinaryHeap* createHeap(int capacity);
void insert(BinaryHeap* heap, int value);
int extractMin(BinaryHeap* heap);
void heapifyUp(BinaryHeap* heap, int index);
void heapifyDown(BinaryHeap* heap, int index);
int getParentIndex(int index);
int getLeftChildIndex(int index);
int getRightChildIndex(int index);
void swap(int *a, int *b);

// Create a binary heap with a given capacity
BinaryHeap* createHeap(int capacity) {
    BinaryHeap *heap = (BinaryHeap*)malloc(sizeof(BinaryHeap));
    heap->data = (int*)malloc(capacity * sizeof(int));
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}

// Insert a value into the heap
void insert(BinaryHeap* heap, int value) {
    if (heap->size == heap->capacity) {
        printf("Heap is full!\n");
        return;
    }
    heap->data[heap->size] = value;
    heap->size++;
    heapifyUp(heap, heap->size - 1);
}

// Extract the minimum element from the heap
int extractMin(BinaryHeap* heap) {
    if (heap->size == 0) {
        printf("Heap is empty!\n");
        return -1;
    }
    int minValue = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return minValue;
}

// Heapify the element at the given index up to maintain heap property
void heapifyUp(BinaryHeap* heap, int index) {
    int parentIndex = getParentIndex(index);
    while (index > 0 && heap->data[index] < heap->data[parentIndex]) {
        swap(&heap->data[index], &heap->data[parentIndex]);
        index = parentIndex;
        parentIndex = getParentIndex(index);
    }
}

// Heapify the element at the given index down to maintain heap property
void heapifyDown(BinaryHeap* heap, int index) {
    int leftChildIndex = getLeftChildIndex(index);
    int rightChildIndex = getRightChildIndex(index);
    int smallest = index;

    if (leftChildIndex < heap->size && heap->data[leftChildIndex] < heap->data[smallest]) {
        smallest = leftChildIndex;
    }
    if (rightChildIndex < heap->size && heap->data[rightChildIndex] < heap->data[smallest]) {
        smallest = rightChildIndex;
    }
    if (smallest != index) {
        swap(&heap->data[index], &heap->data[smallest]);
        heapifyDown(heap, smallest);
    }
}

// Get the index of the parent of the node at index
int getParentIndex(int index) {
    return (index - 1) / 2;
}

// Get the index of the left child of the node at index
int getLeftChildIndex(int index) {
    return 2 * index + 1;
}

// Get the index of the right child of the node at index
int getRightChildIndex(int index) {
    return 2 * index + 2;
}

// Swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Free the memory allocated for the heap
void freeHeap(BinaryHeap* heap) {
    free(heap->data);
    free(heap);
}

// Test the binary heap implementation
int main() {
    BinaryHeap* heap = createHeap(10);

    insert(heap, 10);
    insert(heap, 4);
    insert(heap, 15);
    insert(heap, 20);
    insert(heap, 0);
    insert(heap, 8);

    printf("Extracted Min: %d\n", extractMin());
    printf("Extracted Min: %d\n", extractMin());
    printf("Extracted Min: %d\n", extractMin());
    printf("Extracted Min: %d\n", extractMin());
    printf("Extracted Min: %d\n", extractMin());
    printf("Extracted Min: %d\n", extractMin());

    freeHeap(heap);
    return 0;
}