I got confused while solving the following problem (questions 1–3).


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

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

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

  3. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.

  4. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.

  5. Give an efficient implementation of INCREASE-KEY(A, i, k), which flags an error if k < A[i] = k and then updates the d-ary matrix heap structure appropriately. Analyze its running time in terms of d and n.

My Solution

  1. Give an array $A[a_1 .. a_n]$

    $\qquad \begin{align} \text{root} &: a_1\\ \text{level 1} &: a_{2} \dots a_{2+d-1}\\ \text{level 2} &: a_{2+d} \dots a_{2+d+d^2-1}\\ &\vdots\\ \text{level k} &: a_{2+\sum\limits_{i=1}^{k-1}d^i} \dots a_{2+\sum\limits_{i=1}^{k}d^i-1} \end{align}$

    My notation seems a bit sophisticated. Is there any other simpler one?

  2. Let h denotes the height of the d-ary heap.

    Suppose that the heap is a complete d-ary tree $$ 1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log_d[n{d-1}+1] - 1 $$

  3. This is my implementation:

    1  if A.heapsize < 1
    2      error "heap underflow"
    3  max = A[1]
    4  A[1] = A[A.heapsize]
    5  A.heap-size = A.heap-size - 1
    6  MAX-HEAPIFY(A, 1)
    7  return max
    1  assign depthk-children to AUX[1..d]
    2  for k=1 to d
    3      compare A[i] with AUX[k]
    4      if A[i] <= AUX[k]
    5          exchange A[i] with AUX[k]
    6          k = largest
    7  assign AUX[1..d] back to A[depthk-children]
    8  if largest != i
    9      MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )
    • The running time of MAX-HEAPIFY:

      $$T_M = d(c_8*d + (c_9+..+c_13)*d +c_14*d)$$ where $c_i$ denotes the cost of i-th line above.

    • EXTRACT-MAX: $$ T_E = (c_1+..+c_7) + T_M \leq C*d*h\\ = C*d*(log_d[n(d-1)+1] - 1)\\ = O(dlog_d[n(d-1)]) $$

    Is this an efficient solution? Or there is something wrong within my solution?

  • $\begingroup$ I think there is a slight mistake in the question as well as the explanation: The height of the d-ary heap comes to h = (log [nd − n + 1]) − 1 // NOTE its "-n" and not "-1" and not h = (log [nd−1+1])− 1 Thus we above explanation for height will not hold true. h = log[nd−1+1]−1 = log[nd]-1 = log[n] Although nonetheless, the height of the tree is written as Θ(log(n)). Note: log is always to the base d for a d-ary heap. $\endgroup$ Feb 20, 2015 at 8:21

3 Answers 3

  1. Your solution is valid and follows definition of d-ary heap. But as you pointed out your notation is a bit sophisticated.

    You might use those two following functions to retrieve parent of i-th element and j-th child of i-th element.

    $\text{d-ary-parent}({\it i}) \\ \ \ \ \ {\bf return}\ \lfloor (i-2)/d + 1 \rfloor$

    $\text{d-ary-child}(i, j) \\ \ \ \ \ {\bf return}\ d(i-1)+j+1$

    Obviously $1 \le j \le d$. You can verify those functions checking that $\text{d-ary-parent}(\text{d-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 PARENT, LEFT and RIGHT mentioned in book.

  2. If I understand your answer correctly you use a geometric progression. In your case you get go $h = log_d(n\,d-1+1) - 1$, which is obviously $\log_d(n\,d) - 1 = \log_d(n) + \log_d(d) - 1 = \log_d(n) + 1 - 1 = \log_d(n)$, which in fact is a valid and correct solution. But just for sake of handling constant fluctuations you might wanna write $\Theta(\log_d(n))$.

    The reason for this is that some heaps might not be balanced, so their longest path and shorthest path migt vary by some constant $c$, by using $\Theta$ notation you eliminate this problem.

  3. You don't need to re-implement procedure given in textbook, but you must alter it a bit, eg assigning all children to $AUX$ table using given $\text{d-ary-parent}$ and $\text{d-ary-child}$ functions.

    Because $\text{EXTRACT-MAX}$ was not altered, it depends on running time of $\text{MAX-HEAPIFY}$. In your analysis you now you must use worst-case time proportional to hight and number of children which each node must examine (which is at most d). Once again your analysis is very precise, in the end you got $O(d\ \log_d(n(d-1)))$, which can be transformed to:

    $O(d\ \log_d(n(d-1))) = O(d(\log_d(n) + \log(d-1))) = O(d\ log_d(n) + d\ \log_d(d-1))$

    For practical reasons we can always assume that $d \ll n$, so we can lose the $d \log_d(d-1)$ part of O notation, then we will get $O(d\log_d(n))$. Which is also valid solution. But not surprisingly you can also analyse function run time using Master theorem, which will show that $\text{MAX-HEAPIFY}$ is not only $O$ but even $\Theta$.

  4. CLRS book already provides INSERT procedure. Which looks like this:

    $\text{INSERT}(A, key)\\ \ \ \ \ A.heap\_size = A.heap\_size + 1 \\ \ \ \ \ A[A.heap\_size] = -\infty\\ \ \ \ \ \text{INCREASE-KEY}(A, A.heap\_size, key)$

    It can be easy proven but common sense dictates that it's time complexity is $O(\log_d(n))$. It's because heap might be traversed all the way to the root.

  5. Just like INSERT, INCREASE-KEY is also defined in textbook as:

    $\text{INCREASE-KEY}(A, i, key)\\ \ \ \ \ {\bf if}\ key < A[i]\\ \ \ \ \ \ \ \ \ {\bf error} \text{"new key is smaller then current"}\\ \ \ \ \ A[i] = key\\ \ \ \ \ {\bf while}\ i > 1\ and\ A[i] > A[\text{d-ary-parent}(i)]\\ \ \ \ \ \ \ \ \ A[i] \leftrightarrow A[\text{d-ary-parent(i)}]\\ \ \ \ \ \ \ \ \ i = \text{d-ary-parent(i)}$

    Complexity is obviously $O(\log_d(n))$ (see previous point).

  • $\begingroup$ thanks! How about the implementation of INCREASE-KEY and INSERT? I try to write it, but it gave twice recursive call of MAX-HEAPIFY. Is there a better solution? I found little information on web and wiki $\endgroup$
    – lucasKo
    Oct 16, 2012 at 14:53
  • $\begingroup$ Is that rest of exercise? If so please update your question and I'll be happy to answer theme. $\endgroup$ Oct 16, 2012 at 16:52
  • $\begingroup$ I put those question on the edited post. $\endgroup$
    – lucasKo
    Oct 16, 2012 at 23:21
  • $\begingroup$ reimplment the INSERT procedure? You mean, it doesn't have to call the procedure that adjusts the order within the heap, after inserting a new element? I don't get it... $\endgroup$
    – lucasKo
    Oct 18, 2012 at 1:19
  • $\begingroup$ That description was a bit unfortunate, see edits for clearification. $\endgroup$ Oct 18, 2012 at 14:59

This is not complete answer. part b) solution is not $$h=log_d[n{d-1}+1] - 1$$ Its $$ 1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log_d[n(d-1)+1] - 1$$ as pointed out by user 55463(because he cant comment,but answer),but downvoted because of lack of explanation. Upvoted answer has also mistakenly solved it. Answer will still be $$h=\Theta(\log_d(n))$$ Source:Problem 2-2. Analysis of d -ary heaps ,part b)


Answer to the second question is h = logd(n(d-1) + 1) - 1 So, h = logd(nd - n + 1) - 1

  • 4
    $\begingroup$ Why is this the answer? A formula with no explanation doesn't really help anyone. $\endgroup$ Jul 30, 2016 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.