Bissoy.com
Doctors Medicines MCQs Q&A

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is Correct Answer Ω (log n)

Consider complete binary tree where left and right subtrees of the root are max-heaps given below

To convert the tree into a heap which is possible by calling MAX-HEAPIFY at root. MAX- HEAPIFY operation takes time as the height of the tree. i.e. if we have n elements in the tree then log(n) is the height of the tree.

Step 1: Swap 10 and 40

Step 2: swap 10 and 25

The above tree is a MAX-HEAP

To convert this into a max heap it takes only 2 swap and 2 comparison which is nothing but the height of the tree. So, log(n) time is required to convert the tree into a heap.

Related Questions

If a + b + c + d = 4, then find the value of $$\frac{1}{{\left( {1 - a} \right)\left( {1 - b} \right)\left( {1 - c} \right)}}$$     + $$\frac{1}{{\left( {1 - b} \right)\left( {1 - c} \right)\left( {1 - d} \right)}}$$     + $$\frac{1}{{\left( {1 - c} \right)\left( {1 - d} \right)\left( {1 - a} \right)}}$$     + $$\frac{1}{{\left( {1 - d} \right)\left( {1 - a} \right)\left( {1 - b} \right)}}$$     is?
If a + b + c + d = 4, then the value of $$\frac{1}{{\left( {1 - a} \right)\left( {1 - b} \right)\left( {1 - c} \right)}}$$     + $$\frac{1}{{\left( {1 - b} \right)\left( {1 - c} \right)\left( {1 - d} \right)}}$$     + $$\frac{1}{{\left( {1 - c} \right)\left( {1 - d} \right)\left( {1 - a} \right)}}$$     + $$\frac{1}{{\left( {1 - d} \right)\left( {1 - a} \right)\left( {1 - b} \right)}}$$     is?
Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node III. A max-heap can be constructed from a binary search tree in Θ(n) time IV. A binary search tree can be constructed from a max-heap in Θ(n) time Which of the above statements are TRUE?
Which of the following is/are correct about a strictly binary tree? A. A binary tree is called strictly binary tree if every non-­leaf node of it has non empty left and right sub tree B. In strictly binary tree can have two children or no child C. A strictly binary tree with n leaves always contact 2n­-1 nodes
The Hamiltonian of a particle is given by $$H = \frac{{{p^2}}}{{2m}} + V\left( {\left| {\overrightarrow {\bf{r}} } \right|} \right) + \phi \left( { + \left| {\overrightarrow {\bf{r}} } \right|} \right)\overrightarrow {\bf{L}} .\overrightarrow {\bf{S}} ,$$        where $$\overrightarrow {\bf{S}} $$ is the spin, $$V\left( {\left| {\overrightarrow {\bf{r}} } \right|} \right)$$  and $$\phi \left( {\left| {\overrightarrow {\bf{r}} } \right|} \right)$$  are potential functions and $$\overrightarrow {\bf{L}} \left( { = \overrightarrow {\bf{r}} \times \overrightarrow {\bf{p}} } \right)$$   is the angular momentum. The Hamiltonian does not commute with
The value of the expression $$\frac{{{{\left( {a - b} \right)}^2}}}{{\left( {b - c} \right)\left( {c - a} \right)}} + $$   $$\frac{{{{\left( {b - c} \right)}^2}}}{{\left( {a - b} \right)\left( {c - a} \right)}} + $$    $$\frac{{{{\left( {c - a} \right)}^2}}}{{\left( {a - b} \right)\left( {b - c} \right)}}$$   = ?
$$\frac{{{{\left( {4.53 - 3.07} \right)}^2}}}{{\left( {3.07 - 2.15} \right)\left( {2.15 - 4.53} \right)}} + \, $$     $$\frac{{{{\left( {3.07 - 2.15} \right)}^2}}}{{\left( {2.15 - 4.53} \right)\left( {4.53 - 3.07} \right)}} + \,\, $$     $$\frac{{{{\left( {2.15 - 4.53} \right)}^2}}}{{\left( {4.53 - 3.07} \right)\left( {3.07 - 2.15} \right)}}$$     is simplified to :
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element? 
Consider the differential equation $$\frac{{{{\text{d}}^2}{\text{y}}\left( {\text{t}} \right)}}{{{\text{d}}{{\text{t}}^2}}} + 2\frac{{{\text{dy}}\left( {\text{t}} \right)}}{{{\text{dt}}}} + {\text{y}}\left( {\text{t}} \right) = \delta \left( {\text{t}} \right)$$      with $${\left. {{\text{y}}\left( {\text{t}} \right)} \right|_{{\text{t}} = 0}} = - 2$$   and $${\left. {\frac{{{\text{dy}}}}{{{\text{dt}}}}} \right|_{{\text{t}} = 0}} = 0.$$
The numerical value of $${\left. {\frac{{{\text{dy}}}}{{{\text{dt}}}}} \right|_{{\text{t}} = 0}}$$   is
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root. int height (treeptr n) { if (n == NULL) return -1;   if (n →  left == NULL)        if (n →  right == NULL) return 0;        else return ; \(\boxed{B1}\);     // Box 1 else { h1 = height (n →  left);          if (n → right == NULL) return (1+h1);          else { h2 = height (n → right);          return ; \(\boxed{B2}\)   // Box 2                        }            } } The appropriate expressions for the two boxes B1 and B2 are