GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
67 views

Consider a complete Binary Tree ‘T’ with key of root node be ‘P’. It is given that the left and right subtree of ‘P’ satisfies min-heap property. What is the time taken to convert the given tree ‘T’ to a max heap ?

a)O(log N)

b) O(N)

asked in DS by Veteran (51.8k points)   | 67 views

Apply Build_Max_Heap procedure on the tree, which takes O(N) time.

if the question is

Consider a complete Binary Tree ‘T’ with key of root node be ‘P’. It is given that the left and right subtree of ‘P’ satisfies min-heap property. What is the time taken to convert the given tree ‘T’ to a min heap ?

 

then answer should be log N, rt?

@Sreshtha
yes, then answer will be log(n), call min-heapify function on root which takes logn time
thank u :)

1 Answer

+1 vote

The answer should be O(N)  as we need to to heapify all the nodes in botton up fashion.

answered by (295 points)  

Related questions

+1 vote
1 answer
2
asked in DS by srestha Veteran (51.8k points)   | 47 views
0 votes
0 answers
3
asked in DS by vaishali jhalani Boss (6k points)   | 28 views
Top Users Feb 2017
  1. Arjun

    5502 Points

  2. Bikram

    4266 Points

  3. Habibkhan

    3972 Points

  4. Aboveallplayer

    3046 Points

  5. Debashish Deka

    2646 Points

  6. sriv_shubham

    2328 Points

  7. Smriti012

    2270 Points

  8. Arnabi

    2134 Points

  9. sh!va

    1938 Points

  10. mcjoshi

    1752 Points

Monthly Topper: Rs. 500 gift card

20,936 questions
26,054 answers
59,785 comments
22,209 users