The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
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().

please verify this

asked in Algorithms by Veteran (14.8k points) | 87 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 (2.4k 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
+3 votes
2 answers
2
asked in Algorithms by Kapil Veteran (50.8k points) | 682 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,017 questions
36,845 answers
91,385 comments
34,723 users