Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

D-ary heaps: trade shallower ascent for wider extraction

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A d-ary min-heap stores a complete tree in one array. For zero-based position I, its parent is floor((I - 1) / D), and its children occupy D times I plus one through D times I plus D. Insertion bubbles a new entry toward the root. Extraction saves the root, moves the last entry down the cheapest-child path, and returns the root task. This program requires D at least two. Each entry carries a unique insertion sequence after the priority, so equal priorities leave in arrival order and incident identifiers are never compared. It implements push and pop only; there is no decrease-key operation or deletion of an arbitrary pending incident.

Operational case

A four-way heap receives pump at priority 47, valve at 19, sensor at 19, and grid at 61. Popping four times returns valve, sensor, pump, grid. Valve wins the tie because it was inserted before sensor. Changing D would alter the array shape and number of child comparisons but should not alter that output order. A queue that stores only priority and an incident object may fail when two priorities tie and the objects cannot be ordered; the sequence field prevents that accidental comparison.

Working Python program

python
class DaryDispatchHeap:
    def __init__(self, arity=4):
        if arity < 2:
            raise ValueError("arity must be at least two")
        self.arity = arity
        self.values = []
        self.serial = 0

    def push(self, priority, incident_id):
        self.serial += 1
        entry = (priority, self.serial, incident_id)
        self.values.append(entry)
        child = len(self.values) - 1
        while child:
            parent = (child - 1) // self.arity
            if self.values[parent] <= entry:
                break
            self.values[child] = self.values[parent]
            child = parent
        self.values[child] = entry

    def pop(self):
        if not self.values:
            raise IndexError("empty dispatch heap")
        winner = self.values[0]
        last = self.values.pop()
        if self.values:
            parent = 0
            size = len(self.values)
            while True:
                first = parent * self.arity + 1
                if first >= size:
                    break
                best = min(range(first, min(first + self.arity, size)), key=self.values.__getitem__)
                if last <= self.values[best]:
                    break
                self.values[parent] = self.values[best]
                parent = best
            self.values[parent] = last
        return winner[2]


if __name__ == "__main__":
    dispatch = DaryDispatchHeap(4)
    for priority, incident_id in [(47, "pump"), (19, "valve"), (19, "sensor"), (61, "grid")]:
        dispatch.push(priority, incident_id)
    print("order=", [dispatch.pop() for _ in range(4)], sep="")

Output

Output
order=['valve', 'sensor', 'pump', 'grid']

Time, space, and tradeoff

For N pending incidents, insertion crosses at most O(log base D of N) ancestors. Extraction descends the same height but scans up to D children per level, taking O(D log base D of N) comparisons. Peek would be O(1), and storage is O(N). Larger D can shorten the path while increasing work per extraction; the best arity depends on the operation mix and machine behavior. A binary heap is often enough. This Python example uses a range and min call for each child scan, making the comparison cost visible rather than claiming a universal speedup. It does not support a stable reprioritization or indexed decrease key.

Common Mistakes

  • Do not use binary child formulas in a four-way heap.
  • Do not compare incident objects to break equal priorities.
  • Do not claim every larger arity makes extraction faster.
  • Do not advertise decrease-key when the implementation exposes only push and pop.

Connected lessons

Compare its invariant with LFU caches: evict by frequency, then recency, Expiry heaps: invalidate stale TTL records on replacement, Generational slots: reject stale handles after reuse, then run the retention and dispatch audit and operation quiz.

Radix heaps: queue nondecreasing integer priorities adds another queue operation contract.

Huffman trees: assign prefix codes from symbol frequencies adds a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details