menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
Recent Posts
Barc Interview Experience 2020- CSE stream
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Interview experience at IIT Tirupati for MS program winter admission
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Programming
(3.6k)
DS
(1.5k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.3k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent Blog Comments
hi this pdf have gate prevoius year questions or...
Thanks, dude for sharing your experience !! It...
Congratulations, at least you made it to the...
seems like you really enjoyed the process.......
I wrote an email to IISC regarding JEST 2021 but...
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
asked
Feb 13, 2019
in
Programming
gate_forum
108
views
answer
comment
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
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
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)$
answered
Feb 13, 2019
prashant jha 1
comment
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
Please
log in
or
register
to add a comment.
← 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
heap
data-structures
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
heap
binary-heap
algorithms
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
heap
data-structures
binary-heap
algorithms
made-easy-test-series
...