87 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().

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.

selected
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.