java - 是否有具有固定容量和自定义比较器的 PriorityQueue 实现？

Question

相关问题:

• 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?

我有一个非常大的数据集(超过 500 万个项目)，我需要从中获取 N 个最大的 个项目。最自然的方法是使用堆/优先队列只存储前 N 个项目。 JVM(Scala/Java)的优先级队列有几个很好的实现，分别是:

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

前 2 个很好，但它们存储了所有项目，在我的情况下，这会产生严重的内存开销。第三个(Lucene 实现)没有这样的缺点，但正如我从文档中看到的那样，它也不支持自定义比较器，这对我来说毫无用处。

所以，我的问题是:是否有 PriorityQueue 实现 具有 固定容量 和 自定义比较器？

UPD。最后我根据彼得的回答创建了自己的实现:

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;
            }
        }
    }
}

(其中NaturalComparator取自this问题)

Answer 1

你怎么能说 Lucene 不支持自定义比较器？

它的抽象，你必须实现抽象方法lessThan(T a, T b)