Max heap

Question

Conversion of binary search tree into a Max heap takes:

O(n) time

O(nlog n) time

None

Comments

n time to compare n elements in the worst case and logn time to arrange each at correct position node thus takes O (nlogn) time for heapify

Answer 1

Any form of binary search tree can be converted into a complete binary tree in $\Theta(n)$ time.

And heapification of a complete binary tree into a max or a min heap can be done in $\Theta(n)$ time.

Overall , time would be $\Theta(n)$+$\Theta(n)$ = $\Theta(n)$

Comments

It's because binary search tree can be stored in array which will take O (n) time then it can be converted into heap in O (n) time right