Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I would like to find the height of a d-ary heap. Assuming you have an Array that starts indexing at $1$ we have the following:

The parent of a node $i$ is given by: $\left\lfloor\frac{i+1}{d}\right\rfloor$

The $d$ children of a parent at node $i$ are given by: $di-d+1, di-d+2,\ldots di+1$

The height of a heap (which is slightly different than the height of a binary search tree) is a longest path from the root to a leaf. A longest path will always be from the last node in the heap to the root, but how do I calculate this longest path?

My first Idea is to setup a recurrence relation for the height of the tree:

\begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation}

This seems overly-complicated and I feel like the answer is much more simple. Is there a better way to find the height of a $d-$ary heap?

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

A path from the last node to the leaf would always be a longest path. This is because the last node is always at the lowest level in the heap. Now, assume the root is at level $0$. Then the number of nodes at a completely filled level $i$ would be $d^i$.

Let level $k$ be the last completely filled level in the heap. So the number of nodes upto (and including) level $k$ is: $$\sum\limits_{i = 0}^{k}d^i = \frac{d^{k+1} - 1}{d - 1}$$

Now, the last node - the $n^{th}$ node - can either be the last node at level $k$, or it can be in an incomplete level $k+1$. Taking care of these two cases, it can be seen that: $$\frac{d^{k+1} - 1}{d - 1} \le n < \frac{d^{k+2} - 1}{d - 1}$$ $$\Rightarrow k\le \log_d(n(d-1) + 1) - 1 < k+1$$

Now, equality is only if the last node is the last leaf of level $k$, which also has distance $k$ from the root. If not, that is if there is a level $k+1$, then the $\log$ term would not be an integer, and applying the ceiling operator would give the right height of $k+1$. Thus, if the last element of the array is at position $n$, the height of the heap is: $$h = \lceil \log_d(nd - n + 1) \rceil - 1$$ You can change the base of the logarithm using the change of base formula. Note that this is the same method that Yuval gives in his answer.

share|improve this answer
add comment

A different approach is to calculate the number of points $n_d(h)$ in a saturated (maximal) $d$-ary heap of height $h$. Given $n_d(h)$, the height of a $d$-ary heap of size $n$ is the minimal $h$ such that $n_d(h) \geq n$. Given the formula for $n_d(h)$, you should be able to find $h$ explicitly.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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