AlgoScope

d-ary Heap

A heap where each node has d children. Shallower, cheaper decrease-key, costlier extract.

Data structures, data structure, advanced
Swap 8 with 3.42017132313542651268719899node
Swap 8 with 3.42017132313542651268719899node

D-ary Heap: Heapify with three children per node

Decision, step 2 of 6

Heapify: slot 2 holds 8. Its children are slots 7, 8, 9, that is 3 x 2 + 1 onward, holding 3, 19, 9. The smallest child is 3, found with 2 comparisons. 8 is larger, so they swap and the sift continues from slot 7.

Cost

Insert
O(log_d n)
Extract top
O(d log_d n)
Space
O(n)