Finding the height of a d-ary heap

Question

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?

Answer 1

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.

Answer 2

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.