A binary heap in C

The array is the tree: children of i live at 2i+1 and 2i+2.

#include <stddef.h>

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

void heap_push(int *heap, size_t *n, int value) {
    size_t i = (*n)++;
    heap[i] = value;
    while (i > 0) {
        size_t parent = (i - 1) / 2;
        if (heap[parent] <= heap[i]) {
            break;
        }
        swap(&heap[parent], &heap[i]);
        i = parent;
    }
}

int heap_pop(int *heap, size_t *n) {
    int top = heap[0];
    heap[0] = heap[--(*n)];
    size_t i = 0;
    for (;;) {
        size_t left = 2 * i + 1;
        size_t smallest = i;
        if (left < *n && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (left + 1 < *n && heap[left + 1] < heap[smallest]) {
            smallest = left + 1;
        }
        if (smallest == i) {
            break;
        }
        swap(&heap[i], &heap[smallest]);
        i = smallest;
    }
    return top;
}

How it works

1. Pushing sifts the new value up toward the root.
2. Popping moves the last value to the top and sifts it down.
3. Both are logarithmic, with no pointers anywhere.

Keywords and builtins used here

• break
• for
• heap_pop
• heap_push
• if
• int
• return
• size_t
• static
• swap
• void
• while

The run, in numbers

Lines

42

Characters to type

696

Tokens

271

Three-star pace

105 tpm

At the three-star pace of 105 tokens a minute, this run takes about 155 seconds.

Type this snippet

Step 4 of 4 in Trees, tables & heaps, step 14 of 20 in Data structures & algorithms.

← Previous Next →