Priority Queue Comparator 2d Array descending order

Question

I am creating a priority queue and using comparator to make sure things are storing in descending order, but end of the day it does not store the values in descending order.

    int[][] a = {{1,2},{6,5},{3,4}};
    PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    int s1 = (int) (Math.pow(o1[0], 2) + Math.pow(o1[1],2));
                    int s2 = (int) (Math.pow(o2[0], 2) + Math.pow(o2[1],2));
                    return Integer.compare(s2, s1);
//Also tried Integer.compare(s1, s2); it returns in ascending order
                }
            });

When I am adding the values to priorityQueue, I expect this to be added as {6,5}, {3,4}, {1,2}. But it is adding as {6,5}, {1,2}, {3,4}.

for(int i=0; i<a.length;i++) {
            pq.add(a[i]);
        }

What is the mistake am doing above?

Your mistake is rooted in the assumption that elements inside the `PriorityQueue` are stored in the sorted order, which is not true. Have a look https://stackoverflow.com/questions/1795527/how-is-the-java-priority-queue-supposed-to-work — Alexander Ivanchenko, Jul 12 '22 at 17:40
@AlexanderIvanchenko But OP has added a comparator during instantiation. — nice_dev, Jul 12 '22 at 18:04
@nice_dev If we remove the queue it would be `[6, 5][3, 4][1, 2]` and OP says: *"I expect this to be added as `{6,5}, {3,4}, {1,2}`". They also say: *"But it is adding as {6,5}, {1,2}, {3,4}"* it's the order of iterating over the queue via iterator. — Alexander Ivanchenko, Jul 12 '22 at 18:24
@AlexanderIvanchenko You mean he checked via pq.toString() and not by iterating over the queue? — nice_dev, Jul 12 '22 at 18:32
@nice_dev I mean that iterator would give the following order `[6, 5][1, 2][3, 4]` which OP feel confused about. The question is incomplete because it lacks the code which produce the output (I've used `pq.forEach(arr -> System.out.print(Arrays.toString(arr)));`). — Alexander Ivanchenko, Jul 12 '22 at 19:03
@nice_dev I also interpret this phrase *I am creating a priority queue and using comparator to make sure things are **storing** in descending order* as an evidence of misconception on how Heap data structure and `PriorityQueue`, its implementation works. Sense OP expect elements to be **stored** in sorted order. — Alexander Ivanchenko, Jul 12 '22 at 19:05

score 0 · Accepted Answer · answered Jul 12 '22 at 17:50

0

Try to traverse queue:

while (!pq.isEmpty()) {
  System.out.println(Arrays.toString(pq.poll()));
}

[6, 5]
[3, 4]
[1, 2]

answered Jul 12 '22 at 17:50

Arsegg

126
1
10

@nice_dev yes you are correct. before even traversing, I was inspecting the pq object and thought it was sorted. – user2000189 Jul 12 '22 at 18:25
@user2000189, [priority queue](https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html) based on [binary heap](https://en.wikipedia.org/wiki/Binary_heap). – Arsegg Jul 12 '22 at 18:32
@user2000189 Ok, but actually it isn't. You can create your own class and extend PriorityQueue class and override the toString() method to suit your needs. – nice_dev Jul 12 '22 at 18:33
@user2000189, if you want to preserve sorted order then you should use [TreeSet](https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html). – Arsegg Jul 12 '22 at 18:36

Priority Queue Comparator 2d Array descending order

1 Answers1