相关疑难解决方法(0)

有人可以帮助解释如何构建堆是O(n)复杂性？

将项插入堆中O(log n),并且插入重复n/2次(其余为叶,并且不能违反堆属性).所以,这意味着复杂性应该是O(n log n),我想.

换句话说,对于我们"堆积"的每个项目,它有可能必须针对堆的每个级别过滤一次(这是log n级别).

我错过了什么？

我最近参加了一次采访,我被问到"编写一个程序,从10亿个数字中找出100个最大的数字."

我只能给出一个强力解决方案,即以O(nlogn)时间复杂度对数组进行排序并获取最后100个数字.

Arrays.sort(array);

面试官正在寻找更好的时间复杂性,我尝试了其他一些解决方案但未能回答他.有更好的时间复杂度解决方案吗？

相关问题:

• 具有固定大小的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 && …