recategorized by
709 views
1 votes
1 votes

What is the total number of comparisons performed in the creation of max-heap of height $k$ using "insertion method" which involves insertion of a new element in the heap one at a time and bubble up this new node upwards till heap-property is satisfied? (Assume root at level $1$)

  1. $k2^k+2^{k-1}+2$
  2. $k2^{k+1}-2^k+2$
  3. $k2^k-2^{k+1}+2$
  4. None of these
recategorized by

1 Answer

1 votes
1 votes
Insertion Method:
Total number of nodes present present in a binary tree at level $i$ is $2^{i-1}$
Number of comparisons involved for inserting a node at level $i=i-1$
Number of comparisons of all nodes at level $i=(i-1)2^{i-1}$
$\begin{array}{ll} \text{Total number of comparisons } &=\Sigma_{i=1}^k (i-1) 2^{i-1} \\ & = (k-2)2^k +2 \\ & \bigg[ \Sigma_{i=1}^n (i)2^i = (k-1)2^{k+1}+2 \bigg] \\ & = k2^k -2^{k+1}+2 \end{array}$
Answer:

Related questions

1 votes
1 votes
0 answers
3
Applied Course asked Jan 16, 2019
951 views
What is the maximum number of activation records inserted into stack while converting following infix expression to postfix expression is Infix expression: $\text{7+5*3^2...