GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
68 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 (53.1k points)   | 68 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 (305 points)  

Related questions

+1 vote
1 answer
2
asked in DS by srestha Veteran (53.1k points)   | 65 views
0 votes
0 answers
3
asked in DS by vaishali jhalani Boss (6k points)   | 32 views


Top Users Apr 2017
  1. akash.dinkar12

    3796 Points

  2. Divya Bharti

    2716 Points

  3. Deepthi_ts

    2292 Points

  4. rude

    2142 Points

  5. Tesla!

    1888 Points

  6. Kapil

    1786 Points

  7. Sanjay Sharma

    1702 Points

  8. Debashish Deka

    1690 Points

  9. Prashant.

    1624 Points

  10. Arjun

    1614 Points

Monthly Topper: Rs. 500 gift card

22,147 questions
28,145 answers
63,531 comments
24,300 users