How to Implement Max Heap in C: Simple Guide with Example

To implement a max heap in C, create an array to store heap elements and write functions to insert elements and maintain the heap property by "bubbling up" or "heapifying down". Use a heapify function to reorder elements so the parent is always larger than its children.

Syntax

A max heap in C is usually represented as an array. Key functions include:

• insert(): Adds a new element and restores heap order by moving it up.
• heapify(): Fixes the heap from a given index downwards to maintain max heap property.
• extractMax(): Removes the largest element (root) and reorders the heap.

Indexes for parent and children in array:

• Parent index = (i - 1) / 2
• Left child = 2 * i + 1
• Right child = 2 * i + 2

c

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

Example

This example shows how to build a max heap, insert elements, and extract the maximum value.

c

#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 largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

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

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 extractMax(int heap[], int *size) {
    if (*size <= 0) return -1;
    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, 20);
    insert(heap, &size, 5);
    insert(heap, &size, 30);

    printf("Max element: %d\n", extractMax(heap, &size));
    printf("Max element: %d\n", extractMax(heap, &size));

    return 0;
}

Output

Max element: 30
Max element: 20

Common Pitfalls

Common mistakes when implementing max 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.
• Forgetting to "bubble up" after insertion or "heapify" after extraction, breaking the heap property.
• Using zero-based indexing but applying formulas incorrectly.

c

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

/* Right: Increment size before insert */
void insert_right(int heap[], int *size, int value) {
    int i = (*size)++;
    heap[i] = value;
    // bubbling up code here
}

Quick Reference

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

Key Takeaways

Use an array to represent the max heap and maintain size carefully.

Insert by adding at the end and bubbling up to restore heap order.

Extract max by removing root and heapifying down to fix the heap.

Calculate parent and child indexes correctly to avoid errors.

Always update heap size after insertions and extractions.