d-ary heaps: A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
Indexing in the array: The root of the tree is stored at position 0.
The d children of node at position n are stored at positions dn + i for i = 1,...,d.
For example, in a 4-ary heap, the root is at 0, the children of 0 are at 0+1 = 1 through 0+4 = 4, the children of 1 are at 4 + 1 = 5 through 4 + 4 = 8, and so on, as in the figure: 0
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
To find the parent of a node at i, take ⌊((i − 1)/d)⌋. Some examples from the tree above:
parent(8) = ⌊((8 − 1)/4)⌋ = ⌊7/4⌋ = ⌊1.75⌋ = 1 parent(9) = ⌊((9 − 1)/4)⌋ = ⌊2⌋ = 2 parent(10) = ⌊((10 − 1)/4)⌋ = ⌊9/4⌋ = 2
What is the height of a d-ary heap of n elements in terms of n and d?
As can be seen by examining the above figure, the maximum number of elements that can be stored in a d-ary heap of height h is
In the above example, d = 4, h = 2, giving
So it checks out.
To find h, given d and n, we need to find the smallest h such that the above fraction is greater than or equal to n, in other words,
1
Working with that inequality, we want the smallest h such that
and hence
h = ⌈logd(n(d − 1) + 1) − 1⌉
Let’s try that on our example. With d = 4 and n = 21 we get
h = ⌈logd(n(d − 1) + 1) − 1⌉
= ⌈log4((21)(3) + 1) − 1⌉
= ⌈log4(63 + 1) − 1⌉
= ⌈log4(64) − 1⌉
= ⌈3 − 1⌉
= 2
So that works. With one more item, though, d = 4 and n = 22, and we get
h = ⌈logd(n(d − 1) + 1) − 1⌉
= ⌈log4((22)(3) + 1) − 1⌉
= ⌈log4(66 + 1) − 1⌉
= ⌈log4(67) − 1⌉
= ⌈3.033 − 1⌉
= 3
So, yes, with one more item we will need another level in the height of our tree, which is obvious from the example and so our formula checks out here, too.
We follow one path from root to leaf, looping over up to d children at each level, so running time is O(dlogd n). We loop over d, but for a d-ary heap d is a constant and does not depend on the input, so the loop is constant for all inputs, so we could say O(logd n)
Give an efficient implementation of Insert in a d-ary max-heap. Analyze its running time in terms of d and n.
Nothing has to be changed as long as we use the new definition of Parent. Time is O(logd n).
Give an efficient implementation of Increase-Key(A,i,k), which flags an error if k < A[i], but otherwise sets A[i] = k and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.
Nothing has to be changed as long as we use the new definition of Parent. Time is O(logd n).
2
