d-ary Heap
A heap where each node has d children. Shallower, cheaper decrease-key, costlier extract.
D-ary Heap: Heapify with three children per node
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)