GATE CSE
First time here? Checkout the FAQ!
x
0 votes
71 views

 Consider a heap ‘H’. Each key in a heap is randomly increased or decreased by 1. Then we can restore the heap property on H in linear time O(n). The random choices are independent.

True or false??

---------------------------------------------

i dun think we need even O(n) time to restore heap property

take these heaps.first one is unmodified , following min heap property,then second one after inc or dec by 1

to rstore min heap property in second heap,we just need to call min-heapify on the root which will take just logn time.

i dun think there is a need to build the heap again by calling build-heap() function which takes O(n) time and then calling min-heapify().

please verify this

asked in Algorithms by Veteran (12.6k points)   | 71 views

1 Answer

0 votes
Best answer

Property of Min Heap :

The min-heap property is that for every node i other than the root, A[Parent(i)] <= A[i]

Now consider the following case: 

Note : That is BUILD_MIN_HEAP in the picture, please don't mind for the mistake.

$\therefore$ It requires O(n) time in worst case.

answered by Active (1.7k points)  
selected by
thanks @rahul.i did nt think about all the same elements.

and as build_heao() already contains heapify(),so it will take O(n) time only..right?

and if the heap i was considering above,then that would take Ologn) time..right??

Even for the Heap you considered will take O(n) time as we are employing Build_Min_Heap procedure. The algorithm doesn't know whether to apply Build_Min_Heap or Heapify, right?

For the analysis of Build_Min_Heap, look at CLRS, a very good explanation is given.

no noo,i was asking that if i dun use build-heap() in my heap,just restoring using heapify() function,then it will take O(log n) only..

Yes, in that case it works in O(logn) time.

Related questions

+2 votes
2 answers
1
+2 votes
2 answers
2
asked in Algorithms by Kapil Veteran (45k points)   | 352 views


Top Users Mar 2017
  1. rude

    5246 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2732 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1440 Points

  8. Bikram

    1432 Points

  9. Akriti sood

    1420 Points

  10. Sanjay Sharma

    1128 Points

Monthly Topper: Rs. 500 gift card

21,553 questions
26,902 answers
61,258 comments
23,269 users