+1 vote
172 views
From an array of size n , we need to find the k bigger elements. What is the data structure we should use to find k bigger element in best asymptotic complexity?

1.A max heap of size n.

2. A max heap of size k.

3. A min heap of size n.

4.A min heap of size k.
+2

go with ,A max heap of size n. assume K is constant .

0
Time comp. with a) is O(1)..right?
0
O(klogk)
0
why are you assuming that array is already a max-heap?

if already it is max heap and k is constant then yes it will be O(1), otherwise if k is variable, then O(klogn)

but if array is not initially max-heap and k is also not a constant, then it will take O(n + klogn)
0
Yes I think so too. But the answer was option 4 with some explanation I could never comprehend. So just wanted to make sure :)
+1
@Anu sir, if it is already ma-heap and k is constant then to find k max elements, it will take O(1)
0
oh yes i missed it is not min heap initialy.

nitish yes my bad . for constant it will be constant
+3
here size k min heap will be used . i.e. apart of array used k size min heap.

Approch is:

take 1st element of array put in heap.

from next element compare new element of array with heap element , if large then add in heap and delete old element of heap, that take O(1) +O(logk).

by doing this we get time = O(nlogk)

at the end sort heap with n element in O(klogk)

space =O(k) extra
0
yes, i think so.
0
check solution now.
0
same for small element using min heap of size k .
0
@Anu sir

so it should be O(nlogk)... right?
0
yes nitish , we can save lots of extra space.
+1
@joshi_nitish @Anu007

Me too assumed max heap initially ,Thanks for correcting :)
0
@Anu007
Can you illustrate the algorithm with an example ?

1