java - 为优先级队列提供更多元素？

Question

我想知道为什么下面的输出是 [12, 15, 12]？我知道优先级队列通过堆对元素进行排序，但是为什么 12 不放在 15 之前呢？太感谢了! :)

Queue<Integer> q;
q= new PriorityQueue<>();
q.offer(15);
q.offer(12);
q.offer(2);
q.poll();
q.offer(q.peek());
q.peek();
System.out.println(q);

Answer 1

您应该养成查阅 JDK 类的 Javadoc 的习惯。

System.out.println(q)，根据its documentation ，调用 String.valueOf(q)，根据 its documentation调用 q.toString()，根据 its documentation使用 q.iterator() 中的元素顺序，根据 its documentation没有任何特定的顺序。

如果您考虑如何实现优先级队列(通常作为某种堆结构)，这是有道理的:堆不跟踪元素的顺序，除了确保每个节点都有较小的顺序值大于其所有后代节点。要以有意义的顺序返回元素，最坏情况下需要 O(n log n) 时间。