Binary Heap / Priority Queue (C)
Topics: data structures, heaps, implicit trees
Problem
Implement a binary min-heap (a priority queue) of int over caller-provided
storage (no allocation). The smallest element must always be retrievable in O(1)
and removable in O(log n).
typedef struct { int *data; size_t cap; size_t count; } MinHeap;
void heap_init(MinHeap *h, int *storage, size_t cap);
bool heap_push(MinHeap *h, int x); // false if full
bool heap_peek(const MinHeap *h, int *out); // min without removing; false if empty
bool heap_pop(MinHeap *h, int *out); // remove min; false if empty
size_t heap_len(const MinHeap *h);
Key concepts
- The tree is the array. No nodes, no pointers: for the element at index
i,
its children are 2i+1 and 2i+2 and its parent is (i-1)/2. A heap is just an
array read as a complete binary tree.
- Push sifts up. Append at the end, then swap with the parent while it is
larger, walking toward the root until the heap property holds.
- Pop sifts down. The min is at index 0. Move the last element to the root,
shrink, then swap it with its smaller child while a child is smaller, walking
toward a leaf.
- The invariant: every parent is
<= its children. That is weaker than full
sorting, which is exactly why insert and remove are O(log n) instead of O(n).
Draining the heap with repeated pops yields the elements in sorted order (heapsort).
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/heap && /tmp/heap
Sign in to submit your solution.