recategorized by
4,095 views
0 votes
0 votes

I. A heap is always nearly complete tree.

II. Worst case complexity of heapify operation is O( log n)

III. Worst case complexity of build heap operation is O( n log n)


a. I only

b. I and II only

c. II and III only

d. I, II and III

recategorized by

2 Answers

Best answer
2 votes
2 votes
  1. A heap is a complete binary tree - saying as nearly or almost is confusing. In a complete binary tree last level may not be full but filling must be from left to right. Probably the question asker is looking for "yes" here. 
  2. True. 
  3. Build heap for $n$ elements is $\Theta(n)$ and proof is given in Cormen. Now, if we use big-O notation, we can replace $n$ with any function having same or larger growth rate as $n$. So, worst case time complexity of build-heap operation is $O(n \log n)$ $(O(n), O(n^2), O(n^3)\dots$ are also correct $)$
selected by
2 votes
2 votes
All three are correct.

1) heap is an almost complete binary tree.

2) heapify worst case complexity is equal to the height of the tree. i.e O (log n)

3) for bulding a heap we perfrom heapfiy starting from the first non leaf node(n/2 th index) to root 1. Hence worst case is n/2*logn i.e O(nlogn)

Related questions

5 votes
5 votes
1 answer
1
11 votes
11 votes
5 answers
2
Vikrant Singh asked Dec 28, 2014
3,611 views
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?$\Theta(1)$$\Theta (\log n)$$\Theta (n)$$\Theta (n \log n)$
1 votes
1 votes
1 answer
3
0 votes
0 votes
1 answer
4
saurav raghaw asked Dec 22, 2018
674 views
The time complexity of the most efficient algorithm to determine whether an arbitrary array of size ‘n’, is min-heap or not?(A) O(log n)(B) O(n)(C) O(n logn)(D) O(1)