Binary Heap

Trees O(log n) O(n)

A complete binary tree stored in an array; push sifts a value up and pop sinks the last element down to restore the max-heap order.

heap array

150

PushPops

1/33

Push 15 at the end (index 0).

InvariantEvery parent is ≥ both children, so the maximum is always at the root.

currentcompareinsertremoverotate

heap.c

void siftUp(int h[], int i) {
    while (i > 0 && h[i] > h[(i - 1) / 2]) {
        swap(&h[i], &h[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
 
void push(int h[], int *n, int val) {
    h[*n] = val;
    siftUp(h, (*n)++);
}
 
void siftDown(int h[], int n, int i) {
    for (;;) {
        int l = 2*i+1, r = 2*i+2, big = i;
        if (l < n && h[l] > h[big]) big = l;
        if (r < n && h[r] > h[big]) big = r;
        if (big == i) break;
        swap(&h[i], &h[big]);
        i = big;
    }
}
 
int pop(int h[], int *n) {
    int top = h[0];
    h[0] = h[--(*n)];
    siftDown(h, *n, 0);
    return top;
}

How Binary Heap works

A complete binary tree packed into an array (children of i at 2i+1, 2i+2). Push bubbles a value up until its parent is bigger; pop moves the last element to the root and sinks it down.

When to use it

Priority queues: schedulers, Dijkstra/Prim, top-k tracking, heapsort.