edited by
7,429 views
37 votes
37 votes

An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

  1. $O (n)$
  2. $O (\log n)$
  3. $O (n \log n)$
  4. $O (n \log \log n)$
edited by

3 Answers

Best answer
32 votes
32 votes
Here we need to call Heapify/ Bubble down/ Percolate down procedure on Root, which in the worst case will take time $O (\log n).$ So $B$ is the correct option.

Other options do not even make sense, because with $O(n)$ we can even build an entire Heap not just heapify on the root. $O (n \log n) \;\&\; O (n \log \log n)$ is more than $O(n)$.
edited by
24 votes
24 votes
The question is saying best case which will be when only one swap will be required which will be order of $1$.
As no option matches just call heapify at the root - $O(\log n)$.
edited by
6 votes
6 votes
Step 1:delete the root and replace it with last element and heapify takes O(log n) Step 2: inserting the deleted element again takes O(log n) time so its O(2log n) and finally O(log n)
Answer:

Related questions

19 votes
19 votes
1 answer
1
Ishrat Jahan asked Oct 31, 2014
6,178 views
Which of the following sequences of array elements forms a heap?$\{23, 17, 14, 6, 13, 10, 1, 12, 7, 5\}$$\{23, 17, 14, 6, 13, 10, 1, 5, 7, 12\}$$\{23, 17, 14, 7, 13, 10, ...
44 votes
44 votes
5 answers
2
Rucha Shelke asked Sep 16, 2014
20,578 views
In a binary max heap containing $n$ numbers, the smallest element can be found in time $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$