CODEWITHSUNDEEP
javaheaptime-complexitybig-o
JaimeAL
JaimeAL

Reputation: 35

Complexity of operations on a fixed-size heap

I'm studying for an upcoming exam and I came across a problem where I had to build and maintain a top 10 of highest integers from an incoming, infinite stream of numbers. I thought I could use a min-heap of fixed-size 10, and, when I receive a new number, I could just check if the minimum is lower than the new incoming number, if so, I'd have to update the heap by sequentially extracting the root until I get a higher value, and then inserting the new number, alongside with the previously popped roots (minus the first one, in order to preserve the fixed-size of 10). Now that I have this heap, I can easily get the top 10 by popping and printing every node in the heap.

I coded a method in Java that would accomplish what I'm saying, with a 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);
    }
}

According to my tests, this code does the job and works as expected. Now, here comes my question. What would the complexity be for these two operations? We have a PriorityQueue, so insert and extract-min operations are logarithmic. But in this case, the size of the heap, "n", is, at most, 10. Does this mean that the complexity then is O(log 10), which is basically constant O(1) time?

Upvotes: 1

Views: 667

Answers (1)

meriton
meriton

Reputation: 70584

Yes; the logarithm of a constant is constant, too.

Often, such algorithms are analyzed by describing their runtime as a function of several variables. For instance, we might say that your algorithm extracts the top k out of n numbers in O(n log k) time and O(k) space.

However, if the value of k is known, we might as well use that fact to simplify our analysis.

Upvotes: 1

Related Questions