The Gateway to Computer Science Excellence
0 votes
64 views
Conversion of binary search tree into a Max heap takes:

O(n) time

O(nlog n) time

None
in Programming by Junior (867 points) | 64 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)$
by Loyal (5.8k points)
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
198,265 comments
104,978 users