Java priority queue oder

Question

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

@CPerkins sorry. Corrected my code. Copied wrong code piece before. — BufBills
– BufBills, Commented Apr 27, 2015 at 18:29

isnot2bad · Accepted Answer · 2015-04-27 18:45:36Z

2

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!

answered Apr 27, 2015 at 18:45

isnot2bad

24.5k2 gold badges32 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java priority queue oder

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related