menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Max heap

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
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

2 votes
1 answer
1
195 views
HEAP (MAX/MIN HEAP)
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 ... of an element in the max heap 10) Insertion of an element in the max heap 11) Insertion of an element in min heap
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
Max Heap
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
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
Max Heap
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 ?
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
Madeeasy Max Heap 2019
Please explain the logic behind this shortcut and when to be used?
Please explain the logic behind this shortcut and when to be used?
asked Jan 13, 2019 in Algorithms Markzuck 571 views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...