是否有具有固定容量和自定义比较器的优先级队列实现？

java scala priority-queue heap

2022-08-31 23:41:19

相关问题：

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

前2个很好，但它们存储了所有项目，在我的情况下，这提供了关键的内存开销。第三（Lucene实现）没有这样的缺点，但正如我从文档中看到的，它也不支持自定义比较器，这使得它对我来说毫无用处。

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

UPD。最后，我根据 Peter 的回答创建了自己的实现：

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

答案 1

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

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

答案 2

您可以使用排序集，例如带有自定义比较器的树集，并在大小达到N时删除最小的。