CLRS Solutions | Problem 6-2

A $d$-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have $d$ children instead of 2 children.

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

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

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

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

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

The key insight is that we maintain the same level-by-level, left-to-right ordering that binary heaps use. The root is still at position 1, and we fill each level completely before moving to the next level. The difference is that each node now has $d$ children instead of 2.

For a node at index $i$, we can compute the indices of its parent and children as follows:

\[\begin{align*} \textsc{Parent}(i) &= \left\lceil \frac{i-1}{d} \right\rceil + 1 = \left\lfloor \frac{i+d-2}{d} \right\rfloor \\ \textsc{Child}_k(i) &= d(i-1) + k + 1 \quad \text{for } k = 1, 2, \ldots, d \end{align*}\]

More specifically, the children of node $i$ are at positions $d(i-1) + 2, d(i-1) + 3, \ldots, d(i-1) + d + 1$.

We can verify this works: the root (node 1) has children at positions $2, 3, \ldots, d+1$. Node 2 has children at positions $d+2, d+3, \ldots, 2d+1$, and so on.

B

Think about how many nodes can fit at each level. A $d$-ary heap has 1 node at level 0 (the root), $d$ nodes at level 1, $d^2$ nodes at level 2, and in general, $d^h$ nodes at level $h$.

A complete $d$-ary heap of height $h$ has $1 + d + d^2 + \cdots + d^h = \frac{d^{h+1} - 1}{d - 1}$ nodes. For a heap with $n$ elements, we have:

\[\begin{align*} n &\leq \frac{d^{h+1} - 1}{d - 1} < d^{h+1} \\ \lg n &< (h+1) \lg d \\ h &> \frac{\lg n}{\lg d} - 1 \end{align*}\]

Similarly, a heap of height $h$ must have at least $1 + d + d^2 + \cdots + d^{h-1} + 1 = \frac{d^h - 1}{d - 1} + 1$ nodes (all levels full except the last, which has at least one node):

\[\begin{align*} n &\geq \frac{d^h - 1}{d - 1} + 1 > d^{h-1} \\ \lg n &> (h-1) \lg d \\ h &< \frac{\lg n}{\lg d} + 1 \\ h &< \log_d n + 1 \end{align*}\]

Therefore, the height of a $d$-ary heap with $n$ elements is $\Theta(\log_d n)$.

C

The $\textsc{Extract-Max}$ operation follows the same pattern as in a binary heap. We replace the root with the last element, decrease the heap size, and then restore the heap property by letting the new root “sink down” to its proper position.

$$\textsc{D-Ary-Max-Heapify}(A, i)$$$$\begin{aligned} 1& \quad largest\,=\,i \\ 2& \quad \textbf{for }\,k\,=\,1\textbf{ to }\,d \\ 3& \quad \qquad child\,=\,\textsc{d}(i - 1)\,+\,k\,+\,1 \\ 4& \quad \qquad \textbf{if }\,child\,\leq\,A.heap\text{-}size\textbf{ and }\,A[child]\,>\,A[largest] \\ 5& \quad \qquad \qquad largest\,=\,child \\ 6& \quad \textbf{if }\,largest\,\ne\,i \\ 7& \quad \qquad \text{exchange}\,A[i]\,\text{with}\,A[largest] \\ 8& \quad \qquad \textsc{D-Ary-Max-Heapify}(A, \, largest) \\ \end{aligned}$$

$$\textsc{D-Ary-Extract-Max}(A)$$$$\begin{aligned} 1& \quad \textbf{if }\,A.heap\text{-}size\,<\,1 \\ 2& \quad \qquad \textbf{error }\text{\textquotedblleft heap underflow\textquotedblright} \\ 3& \quad max\,=\,A[1] \\ 4& \quad A[1]\,=\,A[A.heap\text{-}size] \\ 5& \quad A.heap\text{-}size\,=\,A.heap\text{-}size\,-\,1 \\ 6& \quad \textsc{D-Ary-Max-Heapify}(A, \, 1) \\ 7& \quad \textbf{return }\,max \\ \end{aligned}$$

The key difference from binary heaps is that we must compare the current node with $d$ children instead of just 2.

At each level, $\textsc{D-Ary-Max-Heapify}$ does $O(d)$ work to find the maximum among the node and its $d$ children. The procedure may recur down the height of the tree, which is $O(\log_d n)$.

D

The $\textsc{Insert}$ operation adds a new element at the end of the heap and then bubbles it up to maintain the heap property, just as in a binary heap.

$$\textsc{D-Ary-Heap-Insert}(A, key)$$$$\begin{aligned} 1& \quad A.heap\text{-}size\,=\,A.heap\text{-}size\,+\,1 \\ 2& \quad A[A.heap\text{-}size]\,=\,-\infty \\ 3& \quad \textsc{D-Ary-Heap-Increase-Key}(A, \, A.heap\text{-}size, \, key) \\ \end{aligned}$$

The $\textsc{Insert}$ operation calls $\textsc{D-Ary-Heap-Increase-Key}$, which we analyze next. Since $\textsc{Increase-Key}$ runs in $O(\log_d n)$ time (as we’ll show), $\textsc{Insert}$ also runs in $O(\log_d n)$ time.

E

The $\textsc{Increase-Key}$ operation updates the key of a node and then bubbles it up the tree, comparing with parents along the way.

$$\textsc{D-Ary-Heap-Increase-Key}(A, i, key)$$$$\begin{aligned} 1& \quad \textbf{if }\,key\,<\,A[i] \\ 2& \quad \qquad \textbf{error }\text{\textquotedblleft new key is smaller than current key\textquotedblright} \\ 3& \quad A[i]\,=\,key \\ 4& \quad \textbf{while }\,i\,>\,1\textbf{ and }\,A[\textsc{Parent}(i)]\,<\,A[i] \\ 5& \quad \qquad \text{exchange}\,A[i]\,\text{with}\,A[\textsc{Parent}(i)] \\ 6& \quad \qquad i\,=\,\textsc{Parent}(i) \\ \end{aligned}$$

Each iteration of the while loop moves up one level in the tree, performing $O(1)$ work. The tree has height $O(\log_d n)$, so the while loop executes at most $O(\log_d n)$ times.