Min-heap in C: solved exercise

Min-heap in C: solved exercise

If you searched for a solved min-heap in C, here is the complete array-based implementation: O(log n) insertion, O(log n) extract-min, and the heapify operation that maintains the heap property.

A min-heap is a complete binary tree where each node is less than or equal to its children. It is efficiently represented with an array: the left child of node i is at 2*i+1, the right at 2*i+2, and the parent at (i-1)/2.

Problem statement

Implement a fixed-capacity min-heap supporting:

  1. insert(heap, value): inserts an element and restores the heap property.
  2. extract_min(heap): removes and returns the minimum element.
  3. print(heap): displays the internal array.

Insert the values {5, 3, 8, 1, 4, 2} and extract the minimum three times.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

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

#define MAX_HEAP 64

typedef struct {
    int data[MAX_HEAP];
    int size;
} MinHeap;

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

/* Bubble node i up to its correct position */
static void bubble_up(MinHeap *h, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h->data[parent] <= h->data[i]) break;
        swap(&h->data[parent], &h->data[i]);
        i = parent;
    }
}

/* Push node i down to its correct position */
static void push_down(MinHeap *h, int i) {
    while (1) {
        int smallest = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left  < h->size && h->data[left]  < h->data[smallest]) smallest = left;
        if (right < h->size && h->data[right] < h->data[smallest]) smallest = right;
        if (smallest == i) break;
        swap(&h->data[i], &h->data[smallest]);
        i = smallest;
    }
}

void insert(MinHeap *h, int val) {
    if (h->size >= MAX_HEAP) { fprintf(stderr, "Heap full\n"); return; }
    h->data[h->size++] = val;
    bubble_up(h, h->size - 1);
}

int extract_min(MinHeap *h) {
    if (h->size == 0) { fprintf(stderr, "Heap empty\n"); return -1; }
    int min = h->data[0];
    h->data[0] = h->data[--h->size];
    push_down(h, 0);
    return min;
}

void print_heap(const MinHeap *h) {
    printf("Heap [%d]: ", h->size);
    for (int i = 0; i < h->size; i++) printf("%d ", h->data[i]);
    printf("\n");
}

int main(void) {
    MinHeap h = {.size = 0};
    int vals[] = {5, 3, 8, 1, 4, 2};

    for (int i = 0; i < 6; i++) {
        insert(&h, vals[i]);
        print_heap(&h);
    }

    printf("\nExtracting minimums:\n");
    for (int i = 0; i < 3; i++)
        printf("  extract_min() = %d\n", extract_min(&h));

    printf("\nFinal heap: "); print_heap(&h);
    return 0;
}

Expected output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Heap [1]: 5 
Heap [2]: 3 5 
Heap [3]: 3 5 8 
Heap [4]: 1 3 8 5 
Heap [5]: 1 3 8 5 4 
Heap [6]: 1 3 2 5 4 8 

Extracting minimums:
  extract_min() = 1
  extract_min() = 2
  extract_min() = 3

Final heap: Heap [3]: 4 5 8

Common mistakes

  • Wrong child/parent index formulas: left child = 2*i+1, right child = 2*i+2, parent = (i-1)/2. With 1-based indexing the formulas differ.
  • Not decrementing size before calling push_down in extract_min: if size is not reduced, the last element placed at the root is compared with itself.
  • Confusing min-heap and max-heap: in a min-heap the parent is smaller; in a max-heap it is larger. Only the comparison sign changes.
  • Not validating that the heap is non-empty before extract_min: accessing data[0] when size == 0 is undefined behavior.

Practical use

The min-heap is the underlying structure of priority queues, used in Dijkstra’s algorithm, Huffman encoding, task scheduling by priority, and the heapsort sorting algorithm.

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

Why use an array instead of a pointer-based tree for a heap?

Because a complete binary tree maps perfectly to an array without pointers: parent and child indices are computed arithmetically. This reduces memory usage, improves cache locality, and simplifies the code.

What is the heapify (or build-heap) operation?

It converts an arbitrary array into a valid heap in O(n) by applying push_down to all internal nodes from bottom to top (from n/2 - 1 down to 0). This is more efficient than inserting n elements one by one, which costs O(n log n).

How do you convert a min-heap into a max-heap?

Only the comparisons need to be inverted: in bubble_up, change <= to >=; in push_down, change < to >. The rest of the code stays identical.