# Max-Heap PriorityQueue to keep the k highest items and return them in descending order

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?

• 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? Jan 6 at 17:30
• @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? Jan 6 at 18:04
• 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. Jan 6 at 18:08
• You should edit your question to what you want the insertion time complexity to be. Jan 6 at 18:10
• – D.W.
Jan 6 at 19:27

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.
• @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)$. Jan 6 at 18:22
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)$$.