Heaps

A heap is a complete binary tree stored compactly in an array. In a max-heap, every parent is greater than or equal to its children. In a min-heap, every parent is less than or equal to its children.

Heaps are not search trees. They guarantee that the highest-priority value is at the root, but they do not keep the whole array sorted.

The heap has two separate invariants:

1. Shape invariant: the tree is complete, so the array has no gaps.
2. Order invariant: every parent is at least as large as its children for a max-heap, or at most as large for a min-heap.

Both invariants must hold. A tree can satisfy heap order but not be complete; that is not a binary heap. An array can represent a complete tree but violate parent-child order; that is not a valid heap either.

Array Layout

For a node at index i:

left child  = 2*i + 1
right child = 2*i + 2
parent      = (i - 1) / 2

#define MAX_HEAP 256

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

void heap_init(MaxHeap *h) {
    h->size = 0;
}

Because the tree is complete, there are no gaps in the array. This gives heaps better cache locality than pointer-based trees.

Heap Types

A max-heap is used when the largest priority should be removed first. A min-heap is used when the smallest priority should be removed first. The code is almost identical; comparisons are reversed. Dijkstra’s algorithm uses a min-priority queue because it repeatedly chooses the vertex with the smallest tentative distance. Heapsort commonly uses a max-heap to place the largest remaining item at the end.

Insert

Insert the new value at the end, then move it upward until the heap property is restored.

static void heap_swap(MaxHeap *h, int i, int j) {
    int tmp = h->data[i];
    h->data[i] = h->data[j];
    h->data[j] = tmp;
}

void heap_push(MaxHeap *h, int value) {
    int i = h->size++;
    h->data[i] = value;

    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h->data[parent] >= h->data[i]) break;
        heap_swap(h, parent, i);
        i = parent;
    }
}

The value can move at most the height of the heap, so insertion is O(log n).

The height of a complete binary tree with n nodes is floor(log2 n). That is why sift-up and sift-down are logarithmic.

Remove

The maximum value is always at index 0. To remove it, move the last value to the root, shrink the heap, then sift that value downward.

static void heap_sift_down(MaxHeap *h, int i) {
    for (;;) {
        int left = 2*i + 1;
        int right = 2*i + 2;
        int largest = i;

        if (left < h->size && h->data[left] > h->data[largest]) largest = left;
        if (right < h->size && h->data[right] > h->data[largest]) largest = right;
        if (largest == i) break;

        heap_swap(h, i, largest);
        i = largest;
    }
}

int heap_pop(MaxHeap *h) {
    int max_value = h->data[0];
    h->data[0] = h->data[--h->size];
    heap_sift_down(h, 0);
    return max_value;
}

Removal is O(log n).

Removing from an empty heap is an underflow error. A robust implementation should return a status code, just like stack and queue operations.

Heapify

Inserting n values one by one costs O(n log n). Bottom-up heap construction is faster. Leaves are already valid heaps, so start from the last internal node and sift down toward the root.

void heap_build(MaxHeap *h, const int arr[], int n) {
    h->size = n;
    for (int i = 0; i < n; i++) h->data[i] = arr[i];

    for (int i = n / 2 - 1; i >= 0; i--) {
        heap_sift_down(h, i);
    }
}

This is O(n), not O(n log n), because most nodes are near the bottom and can move only a small number of levels. Only a few nodes near the top can move far.

For [4, 10, 3, 5, 1], bottom-up heapify starts at index 1, then index 0:

initial:      [4, 10, 3, 5, 1]
sift index 1: [4, 10, 3, 5, 1]
sift index 0: [10, 5, 3, 4, 1]

The resulting array is a valid max-heap. It is not sorted.

Priority Queue

A priority queue removes values by priority instead of insertion order. A max-priority queue can be implemented directly with a max-heap:

• insert item: heap_push, O(log n)
• inspect highest priority: data[0], O(1)
• remove highest priority: heap_pop, O(log n)

Dijkstra’s algorithm, event simulation, job scheduling, and Huffman coding all rely on this “always remove the best current candidate” pattern.

Changing Priority

Real priority queues often need to change an existing item’s priority.

• increase-key in a max-heap may require sift-up
• decrease-key in a max-heap may require sift-down
• for a min-heap, those directions reverse

Efficient priority updates require knowing the item’s current index in the heap. Many implementations keep a separate map from item id to heap index. Without that map, finding the item costs O(n), wiping out the benefit of logarithmic repair.

Heap Sort

Heapsort uses the heap structure to repeatedly move the maximum value to the end of the array.

void heap_sort(int arr[], int n) {
    MaxHeap h;
    heap_build(&h, arr, n);

    for (int end = n - 1; end >= 0; end--) {
        arr[end] = heap_pop(&h);
    }
}

This version uses a separate heap object for clarity. In-place heapsort stores the heap in the same array and shrinks the active heap region after each extraction. Both versions run in O(n log n).

Heapsort is O(n log n) in the worst case and uses O(1) auxiliary memory when done in place. It is not stable because heap swaps can reorder equal keys.

Pitfalls

• Thinking a heap is sorted
• Searching arbitrary values as if heap order were BST order
• Forgetting that heapify is O(n), not O(n log n)
• Breaking the shape invariant by leaving gaps in the array
• Using max-heap comparisons when implementing a min-heap
• Updating a priority without repairing heap order

Costs

Exercises

1. Build a max-heap from [4, 10, 3, 5, 1] using bottom-up heapify and show every swap.
2. Insert 12 into the heap and trace the sift-up steps.
3. Remove the max value and trace the sift-down steps.
4. Explain why a heap is good for priority queues but poor for searching arbitrary values.