Is there a PriorityQueue implementation with fixed capacity and custom comparator?

Question

Related questions:

• Java PriorityQueue with fixed size
• How do I use a PriorityQueue?
• get indexes of n smallest elements in an array
• Scala: Is there a way to use PriorityQueue like I would in Java?

I have a very large data set (more than 5 millions items) and I need to get N largest items from it. The most natural way to do it is to use heap/priority queue storing only top N items. There are several good implementations of priority queue for JVM (Scala/Java), namely:

• scala.collection.mutable.PriorityQueue
• java.util.PriorityQueue
• lucene.util.PriorityQueue

First 2 are nice, but they store all the items, which in my case gives critical memory overhead. Third (Lucene implementation) doesn't have such a drawback, but as I can see from documentation it also doesn't support custom comparator, which makes it useless for me.

So, my question is: Is there a PriorityQueue implementation with fixed capacity and custom comparator?

UPD. Finally I've created my own implementation, based on Peter's answer:

public class FixedSizePriorityQueue<E> extends TreeSet<E> {      private int elementsLeft;      public FixedSizePriorityQueue(int maxSize) {         super(new NaturalComparator());         this.elementsLeft = maxSize;     }      public FixedSizePriorityQueue(int maxSize, Comparator<E> comparator) {         super(comparator);         this.elementsLeft = maxSize;     }       /**      * @return true if element was added, false otherwise      * */     @Override     public boolean add(E e) {         if (elementsLeft == 0 && size() == 0) {             // max size was initiated to zero => just return false             return false;         } else if (elementsLeft > 0) {             // queue isn't full => add element and decrement elementsLeft             boolean added = super.add(e);             if (added) {                 elementsLeft--;             }             return added;         } else {             // there is already 1 or more elements => compare to the least             int compared = super.comparator().compare(e, this.first());             if (compared == 1) {                 // new element is larger than the least in queue => pull the least and add new one to queue                 pollFirst();                 super.add(e);                 return true;             } else {                 // new element is less than the least in queue => return false                 return false;             }         }     } } 

(where NaturalComparator is taken from this question)

Answer 1

How can you say Lucene's doesn't support a custom comparator?

Its abstract and you must implement the abstract method lessThan(T a, T b)

Answer 2

You could use a SortedSet e.g. TreeSet with a custom comparator and remove the smallest when the size reachs N.