1,170 views
0 votes
0 votes

 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

1 Answer

Best answer
0 votes
0 votes

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 by

Related questions

2 votes
2 votes
1 answer
3
yes asked Oct 6, 2015
1,326 views
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)
0 votes
0 votes
3 answers
4
radha gogia asked Sep 16, 2015
2,622 views
To sort n randomly generated numbers. One should prefer which sorting algo ,Quick or Heap?