Java优先级队列顺序

Question

导入java.util.Comparator; 导入java.util.PriorityQueue;

公共(public)类 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);
        }



    }

}

我有这样的代码。 在java中，我使用优先级队列来存储值数组。 当我尝试一张一张打印它们时，我希望看到它们按顺序打印。如:1 3 4 5 6 7 8 9。 但为什么我看到“1 3 5 8 4 7 6 10 9”？

当我通过提供另一个比较器来使用reverseOrder时。 结果也很奇怪，那就是 “10 9 7 8 4 5 1 4” 这是为什么？

谢谢

Answer 1

PriorityQueue 不能替代已排序的集合!它只是保证，元素的重复出队(通过 poll())会根据其优先级删除它们，但在内部，元素不需要以完全排序的顺序存储。

JavaDoc 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 PriorityQueue#iterator() :

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

阅读文档通常不会有什么坏处!