Priority Queue (Min-Heap)

A priority queue serves elements by priority, not strict FIFO. A binary min-heap stored in an array gives O(log n) insert and extract-min, and O(1) peek at the minimum.

On this page

Representation — complete binary tree in an array
Operations — push, pop, peek, heap property
Example in C — min-heap with sift up / sift down
Trade-offs — heap vs sorted list vs FIFO queue

1) Heap representation

Array indexing for a binary heap (0-based)
Concept	Meaning	Index rule
`heap[]`	Stores keys in level order	Root at index `0`
Parent of `i`	Node above `i`	`(i - 1) / 2`
Left child	First child	`2*i + 1`
Right child	Second child	`2*i + 2`
`size`	Number of elements	Valid range `0 .. size-1`

2) Key operations

Min-heap priority queue API
Operation	Logic	Typical time
`push(x)`	Put `x` at end, sift up until heap order	O(log n)
`pop()`	Replace root with last, shrink size, sift down from root	O(log n)
`peek()`	Return `heap[0]` without removing	O(1)

Min-heap property: every node’s value is ≤ both children’s values. A max-heap flips the comparison.

3) Example in C

#include <stdio.h>

#define MAX 16

static int heap[MAX];
static int size = 0;

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

static void sift_up(int i) {
    while (i > 0) {
        int p = (i - 1) / 2;
        if (heap[p] <= heap[i]) break;
        swap(&heap[p], &heap[i]);
        i = p;
    }
}

static void sift_down(int i) {
    for (;;) {
        int l = 2 * i + 1, r = 2 * i + 2, sm = i;
        if (l < size && heap[l] < heap[sm]) sm = l;
        if (r < size && heap[r] < heap[sm]) sm = r;
        if (sm == i) break;
        swap(&heap[i], &heap[sm]);
        i = sm;
    }
}

int heap_push(int v) {
    if (size >= MAX) return 0;
    heap[size++] = v;
    sift_up(size - 1);
    return 1;
}

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

int heap_peek(int *out) {
    if (size == 0) return 0;
    *out = heap[0];
    return 1;
}

int main(void) {
    int x;
    heap_push(40); heap_push(10); heap_push(30); heap_push(5);
    if (heap_peek(&x)) printf("peek (min): %d\n", x);
    if (heap_pop(&x))  printf("pop: %d\n", x);
    if (heap_peek(&x)) printf("peek after pop: %d\n", x);
    return 0;
}

Execution summary

After pushes 40, 10, 30, 5 (min at root)
Step	Action	Notes
1	Push 40, 10, 30, 5	Heap reorders so smallest is at index 0
2	`peek`	Prints `peek (min): 5`
3	`pop`	Removes 5, re-heapifies; prints `pop: 5`
4	`peek`	New minimum (e.g. 10) — prints `peek after pop: 10`

Visual (min-heap tree)

        [5]
       /   \
    [10]   [30]
    /
 [40]

Array level-order may differ after operations; tree shape stays a complete binary tree.

4) Trade-offs

Pros — Fast insert/extract by priority; no shifting whole arrays like sorted vector insert.
Cons — Not FIFO among equal priorities unless you tie-break (e.g. sequence numbers).

Compare with circular queue for strict FIFO, and linked-list queue for simple ordering without priorities.

Key takeaway

A heap-backed priority queue is the standard way to implement “best next” scheduling. Keep sift up/down symmetric and index arithmetic consistent for 0-based arrays.

Next up: Deque · Circular queue · All queue topics