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?


migrated from cstheory.stackexchange.com Oct 15 '12 at 4:35

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\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$ – Surabhi Raje Feb 20 '15 at 8:21
  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 '12 at 14:53
  • $\begingroup$ Is that rest of exercise? If so please update your question and I'll be happy to answer theme. $\endgroup$ – Bartosz Przybylski Oct 16 '12 at 16:52
  • $\begingroup$ I put those question on the edited post. $\endgroup$ – lucasKo Oct 16 '12 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 '12 at 1:19
  • $\begingroup$ That description was a bit unfortunate, see edits for clearification. $\endgroup$ – Bartosz Przybylski Oct 18 '12 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$ – David Richerby Jul 30 '16 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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