C Mastery / Heaps and Priority Queues
Part 8 — Data Structures and Algorithms in C

Heaps and Priority Queues

This chapter implements a binary heap and the priority queue built on it.

Why This Matters

A heap gives O(log n) insert and O(1) access to the maximum (or minimum) element — the core of priority queues, which drive schedulers, shortest-path algorithms, event simulation, and top-k problems.

Prerequisites

Core Concept

A binary heap is a complete binary tree stored in an array, satisfying the heap property: each parent is ≥ its children (max-heap) or ≤ (min-heap).

Array layout: for a node at index i (0-based):

Because it is complete, no pointer overhead; the whole heap is one contiguous array.

Examples

Max-heap push and pop

#include <stdlib.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Heap;

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

static void sift_up(Heap *h, size_t i)
{
    while (i > 0) {
        size_t p = (i - 1) / 2;
        if (h->data[p] >= h->data[i]) break;
        swap(&h->data[p], &h->data[i]);
        i = p;
    }
}

static void sift_down(Heap *h, size_t i)
{
    for (;;) {
        size_t l = 2*i + 1, r = 2*i + 2, m = i;
        if (l < h->size && h->data[l] > h->data[m]) m = l;
        if (r < h->size && h->data[r] > h->data[m]) m = r;
        if (m == i) break;
        swap(&h->data[i], &h->data[m]);
        i = m;
    }
}

int heap_push(Heap *h, int v)
{
    /* grow h->data if needed (realloc), then */
    h->data[h->size] = v;
    sift_up(h, h->size);
    h->size++;
    return 0;
}

int heap_pop(Heap *h, int *out)
{
    if (h->size == 0) return -1;
    *out = h->data[0];
    h->data[0] = h->data[--h->size];
    sift_down(h, 0);
    return 0;
}

How It Works

Insert appends at the end and sift_up restores the heap property by swapping with the parent. Pop returns the root, moves the last element to the root, and sift_down restores the property by swapping with the larger child. Both are O(log n).

Variations

Min-heap vs. max-heap

Reverse the comparison. A min-heap gives the smallest element first.

Build-heap (heapify)

Building a heap from an unsorted array is O(n) by sifting down from the last non-leaf, better than n separate O(log n) inserts.

Other heaps

Binomial, Fibonacci, and pairing heaps offer different trade-offs (e.g., faster decrease-key for Dijkstra).

Common Mistakes

Undefined Behavior

Portability

Under the Hood

The heap is contiguous and cache-friendly, unlike a pointer-based tree. sift_up/sift_down are tight loops the compiler can optimize well.

Practical Usage

Exercises

1. Implement heap_push, heap_pop, and heap_peek. 2. Implement heapify in O(n) from an unsorted array. 3. Convert the max-heap to a min-heap. 4. Use a priority queue to implement a small job scheduler.

Deep Challenge

Implement a priority queue with a decrease_key operation (for Dijkstra), and explain why a simple binary heap with a position index is needed, or why a Fibonacci heap would be better for dense graphs.

References

Verification

verified.`

Progress

Concept checkboxes

Mastery levels

ConceptCurrent level (0–8)Target level
c.ds.heap06
c.ds.priority-queue06
← PrevNext →