Search code examples
javatreeheappriority-queue

How to sort with O(logN) a priority queue with n-elements?

I have a stream of integers, as well as an int k, given by the user. At the end of the program I must print the k highest numbers. I am only allowed to use a priority queue with a capacity of k.

My problem is that when the queue reaches full capacity, the next integer read must replace the lowest in the queue.

How can I keep the queue sorted after insertion, so that I know which int to replace in the next iteration, with O(logn) complexity? I use a swim method (presented bellow), but ,while it will place the new int at the right level, it doesn't keep the queue entirely sorted.

Here's the swim method:

private void swim(int i){
    while (i > 1) {  //if i root (i==1) return
        int p = i/2;  //find parent
        int result = cmp.compare(heap[i], heap[p]);  //compare parent with child
        if (result == 1) return;    //if child <= parent return
        swap(i, p);                 //else swap and i=p
        i = p;
    }
}

To make myself more clear here's an example for k = 3.

Example

1: A = 42 / B = null / C = null

 2: A = 69 / B= 42 / C = null (69 swims upwards)

3: A = 69 / B= 42 / C = 32

 4: A = 69 / B= 42 / C = 32 (no change)

 5: A = 104 / B= 42 / C = 69 (104 is inserted replacing 32, then swims upwards)

 6: A = 104 / B= 42 / C = 93 (93 is inserted replacing 69, remains there)
Solution

  • First of all, you can't keep the PriorityQueue in sorted order; it is similar, if not exactly same as a heap data structure.
    PriorityQueue just grantee the top element is the min OR max according to it is min OR max heap.

    And also you are getting confused between 2 different problems Sorting elements and Finding K max/min elements.

    If you want to Sort elements in a given list of N elements:
    You can't get a better running time than O(N*log(N)) using a comparison based sort algorithm.

    But, if your case is just Finding K min/max elements from a list of N elements:
    You can achieve it in O(N*log(K)) time.

    Please check this question once: Finding the first n largest elements in an array