1
$\begingroup$

I have created a custom implementation for PriorityQueue using max-heap and everything works fine.

But now i want to change it and keep only the k highest objects in the heap after every insertion. I have to use only one instance of my PriorityQueue and no other helping data structure. So my problem is how should i know if the object that I want to insert is "better" than the "worst" in the priority queue. It's max-heap implemention so the get(first) returns the "best" object and the get(last) it is not the "worst" necessarily.

I need to keep the complexity of insertion at O(nlogn).

Any idea?

$\endgroup$
5
  • $\begingroup$ You can get the worst element in $O(k)$ time and check if the item to be inserted is worst than this element or not. But it will make your insertion operation: $O(k)$ time. Do you want to keep $O(\log k)$ time insertion in your implementation? $\endgroup$ Jan 6 at 17:30
  • $\begingroup$ @Inuyashayagami Actually i need it to be not worse than O(nlogn) where n is the total number of my objects. I think if i search for the worst on every insertion it will be O(nklogk). And thats worse than O(nlogn). Am i right? $\endgroup$ Jan 6 at 18:04
  • $\begingroup$ If you search for the worst in every insertion then the complexity would be $O(n k)$ for $n$ insertions. And, yes it would be worse than $O(n \log k)$ for $O(\log k)$ time insertion operation. $\endgroup$ Jan 6 at 18:08
  • $\begingroup$ You should edit your question to what you want the insertion time complexity to be. $\endgroup$ Jan 6 at 18:10
1
$\begingroup$

If what you want is to keep the top $k$ items at all times what you need is a min-heap, not a max-heap. After every insert you should check if the length is longer than $k$, and if yes, pop.

If you use numbers as your priorities you can turn a max-heap into a min-heap by simply negating the priority.

$\endgroup$
5
  • $\begingroup$ Yes that's what i tried but then I can only return the objects in ascending order. $\endgroup$ Jan 6 at 17:54
  • $\begingroup$ @Theo Giannakopoulos You can use both a max heap and a min heap. If you pop an element from the min heap, increase it's priority in the max heap to some maximum and extract it. This maintains the same running time complexity of $O(\log k)$. $\endgroup$
    – STanja
    Jan 6 at 18:22
  • 1
    $\begingroup$ @Theo Giannakopoulos I also suggest to edit your main post that you want to extract your items in descending order. $\endgroup$
    – STanja
    Jan 6 at 18:26
  • $\begingroup$ @STanja Yes i see what you mean, but i have to use only one instance of my PriorityQueue. Thanks anyway. $\endgroup$ Jan 6 at 18:52
  • $\begingroup$ @Theo Giannakopoulos Sorry, missed that while scanning your problem. If you return the entire contents of the priority queue in sorted order, you can also reverse it in linear time to obtain a descending order. $\endgroup$
    – STanja
    Jan 6 at 19:29
0
$\begingroup$

Have you considered min-max heap with fixed size $k$? As before compare the new item to be inserted if it is greater than the minimum, if so call remove-min and insert the new item. To get the elements in descending order you can call remove-max. Insert,remove-min, and remove-max takes $O(log\ n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.