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

Question

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.

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)

It's not really clear what you want to achieve. If the size of the queue is lower `k` the elements ordered by their natural order (default behavior of the PriorityQueue). When the size of the queue is equal to `k` the elements are ordered by there insertion order and the last element is replace by the next added one? Should the previous last element be removed from the queue? — SubOptimal, Dec 17 '15 at 10:56
@SubOptimal. Like you said, the lowest element should be replaced by the next added one(if it is larger). The problem is that sometimes, the wrong element is replaced. In the example, 93 will replace 69 instead of 42. — Marios Ath, Dec 17 '15 at 11:06
Following which rule `104` is set after step 4 at index A and the order of 69 and 42 is swapped? To be inline with what you said at step 5 it should be 69, 42, 104 instead. — SubOptimal, Dec 17 '15 at 11:14
@SubOptimal Sorry, it was a typo. At step 5, 104 is inserted (not 69) at bottom right, replacing 32. Then, swim makes it switch position with 69, which was at top. — Marios Ath, Dec 17 '15 at 11:24
You should review your examples. Now we know where `104` is comming from. But why in step 5 the order of `69,42` (from step 4) becomes `(42,69)` in step 5? Why at step 6 `93` is replacing `69` and not `42`? Which is not in line with your `next integer read must replace the lowest in the queue`. What is your contraint to `java.util.PriorityQueue`? Should all k elements in the queue by are always sorted by their natural order? — SubOptimal, Dec 17 '15 at 11:49
First of all, I should point out that I'm not using the default priority queue, but one I made myself. The reason that the order changes is because new elements are inserted at C. In step 5, 104 and 69 switch places, which is why the order changes. The only method that I have that does anything akin to sorting is Swim.What I'm asking is how to sort the queue so that after each iteration, the lowest element is at C. — Marios Ath, Dec 17 '15 at 12:08

score 3 · Accepted Answer · edited Sep 14 '19 at 05:36

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

It is exactly the same as a heap data structure. – user207421 Dec 17 '15 at 20:31 — user207421, Dec 17 '15 at 20:31

score 0 · Answer 2 · answered Dec 17 '15 at 12:33

Even your comments In step 5, 104 and 69 switch places and so that after each iteration, the lowest element is at C are not consistent. Because in step 5 the lowest value 42 is at B.

Maybe you are looking for a solution similar to this one.

public class FixedCapacityPriorityQueue {

    static class MyPriorityQueue extends PriorityQueue<Integer> {

        private final int capacity;

        public MyPriorityQueue(int capacity) {
            super(capacity, Comparator.reverseOrder());
            this.capacity = capacity;
        }

        @Override
        public boolean add(Integer i) {
            super.add(i);
            if (size() > capacity) {
                Integer lowest = Integer.MAX_VALUE;
                for (Integer next : this) {
                    if (lowest.compareTo(next) > 0) {
                        lowest = next;
                    }
                }
                this.remove(lowest);
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Integer[] stream = {42, 69, 32, 5, 104, 93};

        for (int i = 0; i < stream.length; i++) {
            PriorityQueue queue = new MyPriorityQueue(3);
            System.out.print("added to queue   : ");
            for (int e = 0; e <= i; e++) {
                 System.out.printf("%d ", stream[e]);
                queue.add(stream[e]);
            }
             System.out.println();
            System.out.print("elements in queue: ");
            while (queue.size() > 0) {
                System.out.printf("%d ", queue.poll());
            }
            System.out.printf("%n%n");
        }
    }
}

output

added to queue   : 42 
elements in queue: 42 

added to queue   : 42 69 
elements in queue: 69 42 

added to queue   : 42 69 32 
elements in queue: 69 42 32 

added to queue   : 42 69 32 5 
elements in queue: 69 42 32 

added to queue   : 42 69 32 5 104 
elements in queue: 104 69 42 

added to queue   : 42 69 32 5 104 93 
elements in queue: 104 93 69

score -1 · Answer 3 · edited May 23 '17 at 12:04

You can arrange you data in binary tree and with a binary tree search find the min number its time you want to delete something. The complexity for binary tree search is O(log N) and the insert of an element it has also O(log N) complexity.

Now talking about your constraint on the queue with length k you can transform the binary tree and store it in an array with length k.

You can check this link If I store a binary tree in an array, how do I avoid the wasted space? to take an idea on how to implement your binary tree in an array.

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

3 Answers3