GATE CSE
First time here? Checkout the FAQ!
x
0 votes
63 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 (10.2k points)   | 63 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.5k 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 (40.5k points)   | 284 views
Top Users Jan 2017
  1. Debashish Deka

    8126 Points

  2. sudsho

    5042 Points

  3. Habibkhan

    4706 Points

  4. Vijay Thakur

    4458 Points

  5. Bikram

    4348 Points

  6. saurabh rai

    4212 Points

  7. Arjun

    4010 Points

  8. santhoshdevulapally

    3722 Points

  9. GateSet

    3292 Points

  10. Sushant Gokhale

    3286 Points

Monthly Topper: Rs. 500 gift card

19,122 questions
24,034 answers
52,724 comments
20,276 users