Register

NIELIT 2017 DEC Scientist B - Section B: 31

• retagged by
1,112 views
2 votes
2 votes

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

  1. $\Omega(\log n)$
  2. $\Omega(n\log n)$
  3. $\Omega(n)$
  4. $\Omega(n^2)$
• retagged by
User Avatar

2 Answers

2 votes
2 votes

Simply call Max_Heapify() on the root. A single heapify call will cause the root to percolate down the tree and the maximum height of a complete binary tree is log n.

Therefore, the lower bound for the number of operations to convert the tree to a heap is Ω(logn).

User Avatar
0 votes
0 votes
The answer to this question is simply max-heapify function on root (Max-Heapify(root)). Time complexity of max-heapify is $\omega(Log n)$ as it recurses at most through height of heap.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
3 answers
1
admin asked Mar 30, 2020
1,708 views
NIELIT 2017 DEC Scientist B - Section B: 30
If for a given Binary Search Tree (BST) the pre-order traversal is $41,23,11,31,62,50,73$. Then which of the following is its post-order traversal? $11,31,23,50,73,62,41$ $31,11,23,50,41,62,73$ $11,31,50,23,73,62,41$ $11,31,23,50,62,73,41$
If for a given Binary Search Tree (BST) the pre-order traversal is $41,23,11,31,62,50,73$. Then which of the following is its post-order traversal?$11,31,23,50,73,62,41$$...
User Avatar
0 votes
0 votes
6 answers
3
admin asked Mar 30, 2020
2,451 views
NIELIT 2017 DEC Scientist B - Section B: 2
According to the given language, which among the following expressions does it correspond to ? Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$. $(0+1+0+1+0+1+0+1)^4$ $(0+1)^4$ $(01)^4$ $(0+1+\varepsilon)^4$
According to the given language, which among the following expressions does it correspond to ?Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$.$(0+1+0+1+0...
User Avatar
0 votes
0 votes
2 answers
4
admin asked Mar 30, 2020
2,342 views
NIELIT 2017 DEC Scientist B - Section B: 3
Using bisection method, one root of $x^4-x-1$ lies between $1$ and $2$. After second iteration the root may lie in interval: $(1.25,1.5)$ $(1,1.25)$ $(1,1.5)$ None of the options.
Using bisection method, one root of $x^4-x-1$ lies between $1$ and $2$. After second iteration the root may lie in interval:$(1.25,1.5)$$(1,1.25)$$(1,1.5)$None of the opt...
User Avatar
Link Copied!