Question

Section 4.5.2 describes a way of storing a complete binary tree of n nodes in an array indexed by 1, 2, K, n .

(a) Consider the node at position j of the array. Show that its parent is at position $\left[\frac{j}{2}\right]$and its children are at 2 jand 2 j + 1 (if these numbers are $\mathbf{\le }\mathit{n}$).

(b) What the corresponding indices when a complete d-ary tree is stored in an array?

Figure 4.16 shows pseudocode for a binary heap, modeled on an exposition by R.E. Tarjan. The heap is stored as an array , which is assumed to support two constant-time operations:

• $\left|h\right|$, which returns the number of elements currently in the array;
• ${\mathit{h}}^{\mathbf{-}\mathbf{1}}$, which returns the position of an element within the array.

The latter can always be achieved by maintaining the values of ${\mathit{h}}^{\mathbf{-}\mathbf{1}}$as an auxiliary array.

(c) Show that themakeheapprocedure takesO(n) time when called on a set of elements. What is the worst-case input? (Hint:Start by showing that the running time is at most $\mathbf{\sum }_{\mathbf{1}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathit{l}\mathit{o}\mathit{g}\left(\frac{n}{i}\right)$).

(d) What needs to be changed to adapt this pseudocode to d-ary heaps?

Short answer

(a)It can be shown that the parent position is $\left[\frac{j}{2}\right]$and its children are at2 jand 2j + 1.

(b) The corresponding indices are j = (dp + 2 - d, dp + 1 - d, dp - d, K, dp, dp + 1 ).

(c) Yes, the makeheap takes the given time and the worst case input is reverse order array.

(d) The bubbleup and the minimum child processes can be changed slightly to adapt the pseudocode to d-ary heaps.

Step-by-step solution

Explain binary tree

A tree with at most two children in every node is called as binary tree. A complete binary tree will have two child node for all the nodes on the same level.

Step 2:Show the position of the parent and its children

(a)

Consider that the node j is at the $m^{th}$position of the $K^{th}$level of the tree, that is $j=2^{k=1}-1+m$. At parent node, $\left[\frac{m}{2}\right]=\left[\frac{m+1}{2}\right]$.

Then the index p is ,

$2^{k=2}-1+\left[\frac{m+1}{2}\right]=2^{k=2}+\left[\frac{m-1}{2}\right]$

So, the position of the parent node and its children node are,

$p=\left[\frac{j}{2}\right]\iff j=2p,2p+1$ ……(1)

Therefore, Equation (1) shows the parent and its children’s position.

Calculate the corresponding indices.

(b)

Consider that the j is located at the $m^{th}$position of the $k^{th}$level of the tree. Then position of the j and its parents node index p can be defined as follows.

role="math" localid="1659079911975" $$\begin{gathered} j=\frac{d^{k-1}-1}{d-1}+m \\ p=\frac{d^{k-2}-1}{d-1}+\left[\frac{d-1+m}{d}\right] \end{gathered}$$

Then, it can be simplified as,

$j+d+2=\frac{d^{k-1}-1}{d-1}+d-1-m$

Then the corresponding indices are as follows,

$p=\left[\frac{j+d-2}{d}\right]\iff j=(dp+2-d,dp+1-d,dp-d,K,dp,dp+1).$

Therefore, the corresponding indices when a complete d-ary is stored in an array has been calculated.

Show that the given runtime is achieved and calculate the worst-case input.

(c)

Consider the Figure 4.16 in the text book, and the two constant time operations.

Consider the vertex with the index i, and the height of the tree is logi. The distance from the base of the tree is defined as follows,

$$\begin{gathered} h-\log i=\log n-\log i \\ =\log \left(\frac{n}{i}\right) \end{gathered}$$

Let, T(n) be the time complexity of building heap can be defined as,

$\sum _{i-1}^n\log \left(\frac{n}{i}\right)=\log \left(\prod _{i-1}^n\right)\frac{n}{i},$

Let,

$$\begin{gathered} F\left(n\right)=\prod _{i-1}^n\frac{n}{i}, \\ F(n+1)=F\left(n\right){\left(\frac{n+1}{n}\right)}^n \end{gathered}$$

For, $F\left(n\right)\le c^n$,where c is a constant, and substitute it into the recursive formula.

$c^n{\left(\frac{n+1}{n}\right)}^n\le c^{n+1}$,because $\underset{n\to \infty }{lim}{\left(\frac{n+1}{n}\right)}^n=e$, where $c\ge e$.

Then, it is concluded that $F\left(n\right)=O\left(e^n\right)$.

Therefore, the time complexity is,

$$\begin{gathered} T\left(n\right)=\log F\left(n\right) \\ =O\left(\log \right(e^n\left)\right) \\ =O\left(n\right) \end{gathered}$$

Therefore, the worst case input is reverse order array.

What needs to be changed to adapt this pseudocode to d-ary heaps.

(d)

Considering the index relationship of the parent and child nodes, the bubbleup and the minimum child processes can be changed slightly to adapt the pseudocode to d-ary heaps.

Therefore, the bubbleup and the minimum child processes can be changed slightly to adapt the pseudocode to d-ary heaps.