The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
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.
asked in Algorithms by Active (3.2k points) | 172 views

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

Time comp. with a) is O(1)..right?
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)
Yes I think so too. But the answer was option 4 with some explanation I could never comprehend. So just wanted to make sure :)
@Anu sir, if it is already ma-heap and k is constant then to find k max elements, it will take O(1)
oh yes i missed it is not min heap initialy.

nitish yes my bad . for constant it will be constant
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
yes, i think so.
check solution now.
same for small element using min heap of size k .
@Anu sir

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

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

Please log in or register to answer this question.

Related questions

+5 votes
2 answers
asked Oct 26, 2016 in Algorithms by jenny101 Active (1.1k points) | 469 views
+2 votes
1 answer
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
49,576 questions
54,192 answers
71,147 users