固定大小堆上操作的复杂性

Question

我正在为即将到来的考试学习，我遇到了一个问题，我必须从传入的无限数字流中构建和维护前 10 个最高整数。我想我可以使用一个固定大小为 10 的最小堆，并且当我收到一个新数字时，我可以只检查最小值是否低于新传入的数字，如果是这样，我必须更新堆通过顺序提取根直到我获得更高的值，然后插入新数字以及之前弹出的根（减去第一个，以保留固定大小 10）。现在我有了这个堆，我可以通过弹出和打印堆中的每个节点轻松获得前 10 个。

我在 Java 中编写了一个方法，它可以使用 PriorityQueue 完成我所说的。

public void addNumber(int number){
    if(pq.size() < 10){
        pq.offer(number);
    }
    else if(pq.peek() < number){
        List<Integer> topNumbers = new LinkedList<Integer>();
        while(!pq.isEmpty() && pq.peek() < number){
            topNumbers.add(pq.poll());
        }
        pq.offer(number);
        for(int i = 1; i < topNumbers.size(); i++){
            pq.offer(topNumbers.get(i));
        }
    }
}

public void printTop10(){
    List<Integer> topNumbers = new LinkedList<Integer>();
    while(!pq.isEmpty()){
        topNumbers.add(pq.poll());
    }

    for(int i = 0; i < topNumbers.size(); i++){
        Node thisOne = topNumbers.get(topNumbers.size() - 1 - i);
        System.out.println(thisOne);
        pq.offer(thisOne);
    }
}

根据我的测试，此代码可以正常工作并按预期工作。现在，我的问题来了。这两个操作的复杂度是多少？我们有一个 PriorityQueue，所以 insert 和 extract-min 操作是对数的。但在这种情况下，堆的大小 "n" 最多为 10。这是否意味着复杂度为 O(log 10)，基本上是恒定的 O(1) 时间？

Answer 1

是；常数的对数也是常数。

通常，通过将运行时间描述为多个变量的函数来分析此类算法。例如，我们可能会说您的算法在 O(n log k) 时间和 O(k) space.

中从 n 数字中提取前 k

但是，如果 k 的值是已知的，我们不妨利用这一事实来简化我们的分析。

固定大小堆上操作的复杂性

Complexity of operations on a fixed-size heap

java

heap

big-o

time-complexity