What is a binary heap, and how do you use it as a priority queue or timer queue?
Short answer: A binary heap is a complete binary tree stored in an array where each parent is ≤ its children (min-heap). The smallest element is always at index 0, insertion and removal of the minimum take O(log n) by "sifting" elements up or down, and no pointers or allocation are needed. That makes it a good fixed-size priority queue, for example a software timer queue ordered by expiry time or an event scheduler.
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#define CAP 16
typedef struct { uint32_t expiry; int id; } tmr_t;
static tmr_t heap[CAP];
static int n;
static void swap(int i, int j) { tmr_t t = heap[i]; heap[i] = heap[j]; heap[j] = t; }
bool heap_push(tmr_t t)
{
if (n == CAP) return false;
int i = n++;
heap[i] = t;
while (i > 0 && heap[(i - 1) / 2].expiry > heap[i].expiry) { /* sift up */
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
return true;
}
bool heap_pop(tmr_t *out)
{
if (n == 0) return false;
*out = heap[0];
heap[0] = heap[--n];
for (int i = 0;;) { /* sift down */
int l = 2 * i + 1, r = l + 1, m = i;
if (l < n && heap[l].expiry < heap[m].expiry) m = l;
if (r < n && heap[r].expiry < heap[m].expiry) m = r;
if (m == i) break;
swap(i, m);
i = m;
}
return true;
}
int main(void)
{
tmr_t t[] = { {50, 1}, {10, 2}, {30, 3}, {20, 4}, {40, 5} };
for (int i = 0; i < 5; i++) heap_push(t[i]);
tmr_t x;
while (heap_pop(&x)) printf("t%d@%u ", x.id, x.expiry); /* t2@10 t4@20 t3@30 t5@40 t1@50 */
printf("\n");
return 0;
}
Array layout: for the node at index i, the parent is (i − 1) / 2 and the children are 2i + 1 and 2i + 2.
Timer queue design comparison
| Structure | Insert | Next expiry | Cancel |
|---|---|---|---|
| Unsorted array | O(1) | O(n) | O(1) with index |
| Sorted linked list (FreeRTOS delayed list) | O(n) | O(1) | O(1) |
| Binary heap | O(log n) | O(1) peek, O(log n) pop | O(log n) with stored index |
| Timer wheel (Linux timers) | O(1) | O(1) amortised | O(1) |
| Red-black tree (Linux hrtimers) | O(log n) | O(1) cached leftmost | O(log n) |
Wrap-around note: with 32-bit tick counters, compare expiry times with (int32_t)(a - b) < 0 instead of a < b, so ordering stays correct across overflow (as long as timeouts are less than half the counter range).