search
Log In
0 votes
108 views
Conversion of binary search tree into a Max heap takes:

O(n) time

O(nlog n) time

None
in Programming 108 views
0
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

1 Answer

0 votes
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)$
0
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

Related questions

2 votes
1 answer
1
195 views
what is the time complexity of various problems such as: 1) Creating the heap 2) Getting maximum element in the max heap 3) Getting minimum element in the max heap 4) Getting maximum element in min heap 5) Getting minimum element in min heap 6) Heapify the element 7) ... ) Deletion of an element in the max heap 10) Insertion of an element in the max heap 11) Insertion of an element in min heap
asked Jan 1, 2019 in Programming Hira Thakur 195 views
7 votes
2 answers
2
2.1k views
The number of ways , in which numbers 1,2,3,4,5 can be inserted into binary heap,such that resultant binary heap is max heap ? given ans :8
asked Dec 9, 2016 in Programming minal 2.1k views
1 vote
1 answer
3
103 views
Suppose you have an array A[1...n] of n elements in arbitrary order, the following alternate implementation of build max-heap. This algorithm calls heapify starting at the root and working its way down the tree, instead of the other way around. For the given input A[1,2,3,4] what will be the output ?
asked Nov 6, 2016 in Programming Rohan Mundhey 103 views
1 vote
0 answers
4
571 views
Please explain the logic behind this shortcut and when to be used?
asked Jan 13, 2019 in Algorithms Markzuck 571 views
...