GATE CSE
First time here? Checkout the FAQ!
x
0 votes
75 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 (13.4k points)   | 75 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.8k 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

+3 votes
2 answers
1
+2 votes
2 answers
2
asked in Algorithms by Kapil Veteran (47.9k points)   | 531 views


Top Users Sep 2017
  1. Habibkhan

    6338 Points

  2. Warrior

    2220 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,981 questions
33,556 answers
79,367 comments
31,013 users