相关疑难解决方法(0)

相关问题:

• 具有固定大小的Java PriorityQueue
• 我如何使用PriorityQueue？
• 获取数组中n个最小元素的索引
• Scala:有没有像我在Java中那样使用PriorityQueue的方法？

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

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

前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 && …

我试图了解何时使用这两个数据结构.据我所知,PriorityQueue也实现为树,因为文档说明插入删除和包含的平均时间是O(logn).树集也提供相同的时间复杂度.另外,它们都是非同步的实现.我可以为它们编写比较器,使其像min heap或max heap一样工作.

有人可以指出我使用这两套的条件.

谢谢,

Java中TreeSet方法的计算复杂度是否与AVLTree相同？

具体来说,我想知道以下方法的计算复杂性:1.add 2.remove 3.first 4.last 5. floor 6. higher

用于方法描述的Java Doc:http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

对于AVL树,有所有O(logn)？什么是上述TreeSet方法的复杂性？

以下操作的时间复杂度是java.util.TreeSet多少？

• first()
• last()
• lower()
• higher()

我认为这些是恒定的时间,但API不保证.