CODEWITHSUNDEEP
java
BufBills
BufBills

Reputation: 8113

Java priority queue oder

import java.util.Comparator; import java.util.PriorityQueue;

public class minMaxHeap {

    static class PQsort implements Comparator<Integer> {

        public int compare(Integer one, Integer two) {
            return two - one;
        }
    }

    public static void main(String[] args) {
        int[] ia = { 1, 10, 5, 3, 4, 7, 6, 9, 8 };
        PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>();

        // use offer() method to add elements to the PriorityQueue pq1
        for (int x : ia) {
            pq1.offer(x);
        }
        for(int num : pq1){
            System.out.print(" " + num);
        }
        System.out.println("");

        PQsort pqs = new PQsort();
        PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10, pqs);
        // In this particular case, we can simply use Collections.reverseOrder()
        // instead of self-defined comparator
        for (int x : ia) {
            pq2.offer(x);
        }

        for(int num : pq2){
            System.out.print(" " + num);
        }



    }

}

I have code like this. In java, I am using priority queue to store array of values. When I try to print them one by one, I expect to see them been printed in order. Such as :1 3 4 5 6 7 8 9. But why do I see "1 3 5 8 4 7 6 10 9"?

When I use reversedOrder by giving another comparator. the result is also strange, which is "10 9 7 8 4 5 1 4" Why is that?

Thanks

Upvotes: 0

Views: 111

Answers (1)

isnot2bad
isnot2bad

Reputation: 24464

A PriorityQueue is not a replacement for a sorted collection! It just guarantees, that repeated dequeuing of elements (via poll()) removes them according to their priority, but internally, the elements need not be stored in completely sorted order.

JavaDoc of PriorityQueue:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

JavaDoc of PriorityQueue#iterator():

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

Reading docs usually doesn't hurt!

Upvotes: 2

Related Questions