java - 优先级队列中的已排序与未排序数据 为什么自动排序和排序会等待？

Question

我知道最小堆是类使用的结构，因为它的效率很高。在我看来，当将未排序的数据提供给 PQ 时，它会将其排序到堆中。

但是当它根据compareTo方法输入升序元素时，它会等待在PQ上执行第一个操作后将其排序到堆中。

你知道这是为什么吗？我不明白为什么它不像无序数据那样自动排序。

我附上了一个我认为可以证明我的问题的程序。

输出:

未排序的数据:

[A, B, D, C, L, F, E, J]

A

[B, C, D, J, L, F, E]

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

1

[2, 3, 4, 10, 12, 6, 5]

排序数据:

[A, B, C, D, E, F, G, H]

A

[B, D, C, H, E, F, G]

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

1

[2, 4, 3, 8, 5, 6, 7]

import java.util.PriorityQueue;

public class Queue2
{
    public static void main(String[] args)
    {
        PriorityQueue<String> pQueue = new PriorityQueue<String>();

        pQueue.add("A");
        pQueue.add("C");
        pQueue.add("F");
        pQueue.add("B");
        pQueue.add("L");
        pQueue.add("D");
        pQueue.add("E");
        pQueue.add("J");
        System.out.println(pQueue); 
        System.out.println(pQueue.remove());
        System.out.println(pQueue);

        System.out.println();

        PriorityQueue<Integer> pQueue2 = new PriorityQueue<Integer>();

        pQueue2.add(1);
        pQueue2.add(3);
        pQueue2.add(6);
        pQueue2.add(2);
        pQueue2.add(12);
        pQueue2.add(4);
        pQueue2.add(5);
        pQueue2.add(10);
        System.out.println(pQueue2); 
        System.out.println(pQueue2.remove());
        System.out.println(pQueue2);

        System.out.println();

        PriorityQueue<String> pQueue3 = new PriorityQueue<String>();

        pQueue3.add("A");
        pQueue3.add("B");
        pQueue3.add("C");
        pQueue3.add("D");
        pQueue3.add("E");
        pQueue3.add("F");
        pQueue3.add("G");
        pQueue3.add("H");
        System.out.println(pQueue3); 
        System.out.println(pQueue3.remove());
        System.out.println(pQueue3);

        System.out.println();

        PriorityQueue<Integer> pQueue4 = new PriorityQueue<Integer>();

        pQueue4.add(1);
        pQueue4.add(2);
        pQueue4.add(3);
        pQueue4.add(4);
        pQueue4.add(5);
        pQueue4.add(6);
        pQueue4.add(7);
        pQueue4.add(8);
        System.out.println(pQueue4); 
        System.out.println(pQueue4.remove());
        System.out.println(pQueue4);

    }
}

Answer 1

来自 PriorityQueue 的文档

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

和

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. 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()).

这就是为什么当您打印队列(使用 System.out)时，会使用内部迭代器，因此不能保证排序输出...但是如果您使用 poll()在这两种情况下，您肯定会多次看到对象以有序方式返回