CHow-ToBeginner · 4 min read

How to Implement Min Heap in C: Syntax and Example

To implement a min heap in C, create an array-based binary tree where the parent node is always smaller than its children. Use functions to insert elements, heapify to maintain order, and extract the minimum element efficiently.

📐

Syntax

A min heap in C is typically implemented using an array and these key functions:

insert(): Adds a new element and maintains heap order.
heapify(): Fixes the heap property from a given node downwards.
extractMin(): Removes and returns the smallest element (root).

The array index starts at 0, with parent and child relationships defined as:

Parent index = (child_index - 1) / 2
Left child index = 2 * parent_index + 1
Right child index = 2 * parent_index + 2

void insert(int heap[], int *size, int value);
void heapify(int heap[], int size, int i);
int extractMin(int heap[], int *size);

💻

Example

This example shows how to create a min heap, insert values, and extract the minimum element.

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int heap[], int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left] < heap[smallest])
        smallest = left;
    if (right < size && heap[right] < heap[smallest])
        smallest = right;

    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        heapify(heap, size, smallest);
    }
}

void insert(int heap[], int *size, int value) {
    int i = (*size)++;
    heap[i] = value;

    while (i != 0 && heap[(i - 1) / 2] > heap[i]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

int extractMin(int heap[], int *size) {
    if (*size <= 0) return -1; // empty heap
    if (*size == 1) {
        (*size)--;
        return heap[0];
    }

    int root = heap[0];
    heap[0] = heap[--(*size)];
    heapify(heap, *size, 0);

    return root;
}

int main() {
    int heap[100];
    int size = 0;

    insert(heap, &size, 10);
    insert(heap, &size, 5);
    insert(heap, &size, 20);
    insert(heap, &size, 3);

    printf("Min element: %d\n", extractMin(heap, &size));
    printf("Min element: %d\n", extractMin(heap, &size));

    return 0;
}

Output

Min element: 3 Min element: 5

⚠️

Common Pitfalls

Common mistakes when implementing a min heap in C include:

Not updating the heap size correctly after insertions or extractions.
Incorrect parent or child index calculations causing out-of-bound errors.
Failing to maintain the heap property after insert or extract operations.
Using 1-based indexing instead of 0-based indexing for the array.

Always test heapify and insert functions carefully to ensure the min heap property is preserved.

/* Wrong: Not updating size after insert */
void insert_wrong(int heap[], int *size, int value) {
    int i = *size; // size not incremented
    heap[i] = value;
    // heap property fix omitted
}

/* Right: Increment size and fix heap */
void insert_right(int heap[], int *size, int value) {
    int i = (*size)++;
    heap[i] = value;
    while (i != 0 && heap[(i - 1) / 2] > heap[i]) {
        int temp = heap[i];
        heap[i] = heap[(i - 1) / 2];
        heap[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

📊

Quick Reference

Parent index: (i - 1) / 2
Left child index: 2 * i + 1
Right child index: 2 * i + 2
Insert: Add at end, then bubble up to fix heap
Extract min: Remove root, replace with last element, then heapify down

✅

Key Takeaways

Use an array to represent the min heap with 0-based indexing.

Maintain the heap property by bubbling up on insert and heapifying down on extract.

Always update the heap size after insertions and extractions.

Calculate parent and child indices carefully to avoid errors.

Test heap operations to ensure the min heap property is preserved.