6-2 Analysis of $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.

a. How would you represent a $d$-ary heap in an array?

b. What is the height of a $d$-ary heap of $n$ elements in terms of $n$ and $d$?

c. Give an efficient implementation of $\text{EXTRACT-MAX}$ in a $d$-ary max-heap. Analyze its running time in terms of $d$ and $n$.

d. Give an efficient implementation of $\text{INSERT}$ in a $d$-ary max-heap. Analyze its running time in terms of $d$ and $n$.

e. Give an efficient implementation of $\text{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$.

a. We can use those two following functions to retrieve parent of $i$-th element and $j$-th child of $i$-th element.

 1 2 d-ARY-PARENT(i) return floor((i - 2) / d + 1) 
 1 2 d-ARY-CHILD(i, j) return d(i − 1) + j + 1 

Obviously $1 \le j \le d$. You can verify those functions checking that

$$d\text{-ARY-PARENT}(d\text{-ARY-CHILD}(i, j)) = i.$$

Also easy to see is that binary heap is special type of $d$-ary heap where $d = 2$, if you substitute $d$ with $2$, then you will see that they match functions $\text{PARENT}$, $\text{LEFT}$ and $\text{RIGHT}$ mentioned in book.

b. Since each node has $d$ children, the height of a $d$-ary heap with $n$ nodes is $\Theta(\log_d n)$.

c. $d\text{-ARY-HEAP-EXTRACT-MAX}(A)$ consists of constant time operations, followed by a call to $d\text{-ARY-MAX-HEAPIFY}(A, i)$.

The number of times this recursively calls itself is bounded by the height of the $d$-ary heap, so the running time is $O(d\log_d n)$.

 1 2 3 4 5 6 7 8 d-ARY-HEAP-EXTRACT-MAX(A) if A.heap-size < 1 error "heap under flow" max = A[1] A[1] = A[A.heap-size] A.heap-size = A.heap-size - 1 d-ARY-MAX-HEAPIFY(A, 1) return max 
 1 2 3 4 5 6 7 8 9 d-ARY-MAX-HEAPIFY(A, i) largest = i for k = 1 to d if d-ARY-CHILD(k, i) ≤ A.heap-size and A[d-ARY-CHILD(k, i)] > A[i] if A[d-ARY-CHILD(k, i)] > largest largest = A[d-ARY-CHILD(k, i)] if largest != i exchange A[i] with A[largest] d-ARY-MAX-HEAPIFY(A, largest) 

d. The runtime is $O(\log_d n)$ since the while loop runs at most as many times as the height of the $d$-ary array.

 1 2 3 4 5 6 7 d-ARY-MAX-HEAP-INSERT(A, key) A.heap-size = A.heap-size + 1 A[A.heap-size] = key i = A.heap-size while i > 1 and A[d-ARY-PARENT(i) < A[i]] exchange A[i] with A[d-ARY-PARENT(i)] i = d-ARY-PARENT(i) 

e. The runtime is $O(\log_d n)$ since the while loop runs at most as many times as the height of the $d$-ary array.

 1 2 3 4 5 6 7 d-ARY-MAX-HEAP-INSERT(A, i, key) if key < A[i] error "new key is smaller than current key" A[i] = key while i > 1 and A[d-ARY-PARENT(i) < A[i]] exchange A[i] with A[d-ARY-PARENT(i)] i = d-ARY-PARENT(i)