d-ary heaps

What if every node in a heap had four children, or eight? Watch the same 40 keys flatten into fewer levels.

⋯34int pop(void)35{36    int top = heap[0];37    size--;38    heap[0] = heap[size];39    int i = 0;40    for (;;) {41        int first = D * i + 1;42        if (first >= size)43            break;44        int best = first;45        for (int c = first + 1; c < first + D && c < size; c++) {46            down_cmp++;47            if (heap[c] < heap[best])48                best = c;49        }50        down_cmp++;51        if (heap[i] <= heap[best])52            break;53        swap(&heap[i], &heap[best]);54        i = best;55    }56    return top;57}⋯61    for (int i = 1; i <= N; i++)62        push((i * 37) % 101);63    int height = 0;64    for (long first = 1, level = 1; first < N; level *= D, first += level)65        height++;66    int prev = -1, sorted = 1;67    while (size > 0) {68        int k = pop();69        if (k < prev)70            sorted = 0;71        prev = k;72    }73    printf("d = %d: height %d, up %ld, down %ld, %s\n",74           D, height, up_cmp, down_cmp, sorted ? "sorted" : "NOT sorted");75    return 0;

The same heap, more children

A d-ary heap is a binary heap with d children per node instead of 2. Everything else stays: the tree is complete, filled level by level from the left; it lives in an array, cell 0 the root; and every parent is no larger than its children, so the smallest key is in cell 0.

What changes is the shape. Level 0 holds 1 node, level 1 holds d, level 2 holds d², and so on. With more children per level the levels fill faster, and the tree is shallower: 40 keys need 6 levels with 2 children, 4 with 4, and 3 with 8.

The formulas and the trade

Where the children are

Number the cells from 0. The children of cell i are cells d·i + 1 to d·i + d, and the parent of cell i (for i > 0) is cell ⌊(i − 1)/d⌋. With d = 2 these are the binary heap’s 2i + 1, 2i + 2 and ⌊(i − 1)/2⌋.

void push(int key)
{
    int i = size;
    heap[i] = key;
    size++;
    while (i > 0) {
        int p = (i - 1) / D;
        up_cmp++;
        if (heap[p] <= heap[i])
            break;
        swap(&heap[p], &heap[i]);
        i = p;
    }
}

push is the binary heap’s sift-up with / 2 replaced by / D: one comparison with the parent per level, then a swap or a stop.

The height

The height h is the number of levels under the root. A complete tree of n keys has height h when its first h levels hold fewer than n keys, 1 + d + … + d^(h−1) < n, and h + 1 levels hold all of them. That makes h about log_d n: for 40 keys, 5 with d = 2, 3 with d = 4 and 2 with d = 8. The program counts it the same way, level by level:

int height = 0;
for (long first = 1, level = 1; first < N; level *= D, first += level)
    height++;

first is the cell where the next level starts; while it is inside the heap, there is one more level.

Pop pays d comparisons a level

for (;;) {
    int first = D * i + 1;
    if (first >= size)
        break;
    int best = first;
    for (int c = first + 1; c < first + D && c < size; c++) {
        down_cmp++;
        if (heap[c] < heap[best])
            best = c;
    }
    down_cmp++;
    if (heap[i] <= heap[best])
        break;
    swap(&heap[i], &heap[best]);
    i = best;
}

To sink a key one level, pop first finds the smallest of its children, d − 1 comparisons, then compares the key with it, one more: d comparisons per level. So:

• A push compares at most once per level: at most h comparisons, which shrinks as d grows.
• A pop compares at most d times per level: at most d · h, about d · log_d n, which grows as d grows.

In the three runs, the dearest push made 4, 3 and 2 comparisons for d = 2, 4 and 8, never more than the heights 5, 3 and 2. The first pop made exactly 10, 12 and 16, the full d · h, because the key that replaced 3 was compared on every level: with d = 2 it sank four levels and stayed after comparing on the fifth; with 4 and 8 it sank to the bottom.

Choosing d

A wider heap is not better in every way: it moves cost from pushes to pops. Over all 40 pushes the comparisons going up fell from 72 to 53 to 47, while over all 40 pops the comparisons going down rose from 239 to 284 to 430. For this program, with as many pops as pushes, d = 2 made the fewest in total: 311 against 337 and 477.

So choose d by the workload. When pushes, or keys whose priority falls and must sift up, far outnumber pops, a larger d pays: Dijkstra’s shortest-path algorithm (19.5) is the usual example, and such workloads favour d = 4 or more. Speed on a real machine also depends on memory caches, which a wider node can help; this page measures comparisons, not time.

Worked example

The formulas for d = 4. The children of cell 2 are cells 4·2 + 1 = 9 to 4·2 + 4 = 12, and the parent of cell 12 is ⌊11/4⌋ = 2.

A million keys. log₂ 10⁶ ≈ 19.9, log₄ 10⁶ ≈ 9.97 and log₈ 10⁶ ≈ 6.6. Counting levels as the program does, a heap of 10⁶ keys has height 19 for d = 2, 10 for d = 4 and 7 for d = 8. So a push costs at most 19, 10 and 7 comparisons, and a pop at most 2 · 19 = 38, 4 · 10 = 40 and 8 · 7 = 56. Going from 2 to 4 children halves the push while the pop’s bound barely moves; going on to 8 saves 3 more on a push and costs 16 more on a pop.

A workload heavy in pushes. Say there are ten pushes for every pop on that million-key heap. By the bounds, each round of ten pushes and one pop costs at most 10 · 19 + 38 = 228 comparisons for d = 2, 10 · 10 + 40 = 140 for d = 4 and 10 · 7 + 56 = 126 for d = 8.

Two checks. What is the parent of cell 17 in a 4-ary heap? (Cell 4, since ⌊16/4⌋ = 4.) How many levels do 100 keys need with d = 10? (3: they hold 1, 10 and the remaining 89.)

Where it’s used

Shortest paths. On dense graphs, Dijkstra’s algorithm (19.5) can lower vertices’ distances far more often than it pops one; each lowering is a sift-up, so 4-ary heaps are a common choice.

Timers. Event loops and operating systems keep pending timers in a priority queue ordered by firing time; where timers are added far more often than they fire, a wider heap suits the workload.

Memory. With d = 4 or 8, a node’s children sit side by side in the array, and a pop reads them together; whether that is faster has to be measured on the machine at hand.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.