Min Priority Queue and Max Priority Queue not sorting correctly

Question

I am coding a Min Priority Queue and a Max Priority Queue like the following:

PriorityQueue<Double> max_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1<o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

        PriorityQueue<Double> min_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1>o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

Numbers of an input array are added one by one to the queue. However, when the array [12,4,5,3,8,7] is a sample input and the output of printing the priority queues is:

MIN: [3.0, 4.0, 5.0, 12.0, 8.0, 7.0] MAX: [12.0, 8.0, 7.0, 3.0, 4.0, 5.0]

Is there something wrong with the comparator I defined? Thanks in advance for your help.

Answer 1

When you iterate over the elements of a PriorityQueue those elements are not completely ordered. The only thing you can be sure of is that a PriorityQueue will enforce that the smallest and biggest elements are the first elements of the min_pq and max_pq priority queues, respectively.

From the PriorityQueue javadocs:

The head of this queue is the least element with respect to the specified ordering.

Based on that assumption you can print in order if you use the method poll():

while(!max_pq.isEmpty())
{
    System.out.println(max_pq.poll());
}

The poll method:

Retrieves and removes the head of this queue, or returns null if this queue is empty.

For comparing Doubles you should use the method Double.compare(o1, o2). Moreover, you can simplify your comparators using lambda and method references, namely instead of :

PriorityQueue<Double> max_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1<o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

        PriorityQueue<Double> min_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1>o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

you can use the more elegant and simple:

PriorityQueue<Double> max_pq = new PriorityQueue<>(Double::compareTo);
PriorityQueue<Double> min_pq = new PriorityQueue<>((o1, o2) -> Double.compare(o2, o1));

Alternatively, instead of PriorityQueue, you could opt for a TreeSet, and there you can iterate over the elements in the order based on the comparator that you have chosen, without having to remove any element.

TreeSet<Double> max_pq = new TreeSet<>(Double::compareTo);

Another benefit of the TreeSet is that it comes with the method descendingSet(). Therefore, you do not need to keep two data structures to keep both the min and max order, instead you can have just:

  TreeSet<Double> max_pq = new TreeSet<>(Double::compareTo);
   
  max_pq.forEach(System.out::println);
  max_pq.descendingSet().forEach(System.out::println);