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

Related questions

+1 vote
1 answer
2
asked in DS by srestha Veteran (56.5k points)   | 90 views
0 votes
0 answers
3
asked in DS by vaishali jhalani Boss (6.1k points)   | 39 views


Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3120 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,969 questions
32,072 answers
74,565 comments
30,147 users