How to Implement Heap in C: Syntax, Example, and Tips

To implement a heap in C, create an array to store elements and write functions to insert, delete, and heapify nodes maintaining the heap property. Use a binary heap structure where the parent node is always greater (max-heap) or smaller (min-heap) than its children.

Syntax

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

• insert(): Add a new element and maintain heap order.
• heapify(): Fix the heap property from a given node downwards.
• extract(): Remove the root element (max or min) and re-heapify.

Indexes for parent and children in array:

• Parent index = (i - 1) / 2
• Left child index = 2 * i + 1
• Right child index = 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 a max-heap implementation with insert, heapify, and extract functions. It inserts values, prints the heap, extracts the max, and prints the heap again.

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;
}

void printHeap(int heap[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", heap[i]);
    printf("\n");
}

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

    insert(heap, &size, 10);
    insert(heap, &size, 20);
    insert(heap, &size, 5);
    insert(heap, &size, 30);
    insert(heap, &size, 15);

    printf("Heap array after inserts: ");
    printHeap(heap, size);

    int max = extractMax(heap, &size);
    printf("Extracted max: %d\n", max);

    printf("Heap array after extracting max: ");
    printHeap(heap, size);

    return 0;
}

Output

Heap array after inserts: 30 20 5 10 15 
Extracted max: 30
Heap array after extracting max: 20 15 5 10 

Common Pitfalls

Common mistakes when implementing heaps in C include:

• Not updating the heap size correctly after insert or extract.
• Incorrect parent or child index calculations causing out-of-bound errors.
• Forgetting to heapify after extraction, which breaks the heap property.
• Mixing max-heap and min-heap logic unintentionally.

Always test boundary cases like empty heap or single element heap.

c

/* Wrong: Not heapifying after extract */
int extractMaxWrong(int heap[], int *size) {
    if (*size <= 0) return -1;
    int root = heap[0];
    heap[0] = heap[--(*size)];
    // Missing heapify call here
    return root;
}

/* Right: Call heapify to fix heap */
int extractMaxRight(int heap[], int *size) {
    if (*size <= 0) return -1;
    int root = heap[0];
    heap[0] = heap[--(*size)];
    heapify(heap, *size, 0);
    return root;
}

Quick Reference

Remember these key points when working with heaps in C:

• Use array indexing: parent = (i-1)/2, left child = 2*i+1, right child = 2*i+2.
• Insert by adding at the end and bubbling up.
• Extract max/min by swapping root with last element, reducing size, and heapifying down.
• Heapify fixes the heap property from a node downwards.

Key Takeaways

Implement heaps in C using arrays and maintain heap property with insert and heapify functions.

Use correct parent and child index calculations to avoid errors.

Always heapify after extracting the root to keep the heap valid.

Test edge cases like empty or single-element heaps to ensure robustness.