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 &quot;better&quot; than the &quot;worst&quot; in the priority queue. It's max-heap implemention so the get(first) returns the &quot;best&quot; object and the get(last) it is not the &quot;worst&quot; necessarily.
I need to keep the complexity of insertion at O(nlogn).
Any idea?
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.