Finding the height of a d-ary heap

Problem Detail: 

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?

Asked By : CodeKingPlusPlus

Answered By : Paresh

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9914