Java 优先队列问题

[yuanyuandeqiu]

这样一段程序：

public static void main(String[] args) {
int[] reward = new int[]{1, 4, 4, 6, 4};
Queue<Integer> q1 = new PriorityQueue<>();
Queue<Integer> q2 = new PriorityQueue<>((a, b) -> b - a);
for (int j : reward) {
q1.add(j);
}
for (int j : reward) {
q2.add(j);
}
System.out.println(q1);//[1, 4, 4, 6, 4]
System.out.println(q2);//[6, 4, 4, 1, 4]
}

请教各位，为什么会排序错误

[Zakl21]

直接 print 不一定有序的，你试试 while true pop 打印

[Nazz]

正确的姿势是:

while(q.len() >0) {
println(q.pop())
}

[yuanyuandeqiu]

@Nazz
@Zakl21
感谢，那 debug 的时候是不是也是无序的

[yuanyuandeqiu]

debug 的时候 q 的顺序和 System.out.println 打印出来的一致，这是为什么

[Nazz]

好好看看数据结构基础吧

[jamezee]

看下类的注释就知道了
An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
...

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()).

[yuanyuandeqiu]

@Nazz
@jamezee
感谢

[fengpan567]

while(q2.peek() != null) {
println(q.poll());
}

[azusachino]

优先队列只保证最大 /小堆，不保证顺序； online challenge 挂了之后，一查才知道。。。

[Koril]

System.out.println(q1) 应该是调用了 AbstractCollection 里的 toString()，里面的逻辑就是拿子类的 iterator 去做遍历，所以看看 PriorityQueue 的 iterator 方法，就知道为什么打印出来是这个顺序了，因为优先队列是维护二叉小顶堆，所以单纯的去按照内部维护的数组的顺序，是没法打印出优先队列的正确顺序的。改用 pop() 打印出来就对了。
另外，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()).

[nerkeler]

[6, 4, 4, 1, 前四个是因为构造方法传了自定义比较器，最后一个 4 位置按照可能是按照比较器取 a,b 得方式，我看最后一个传值 4 比较得是前面得 4 而不是最后得 1 。
上面得说打印得纯属误人子弟，为什么我这么说，因为我 debug 一步一步看的

追到源码，是这一段重排了顺序：
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}

[nerkeler]

看错了，是这一段
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
你可以自己顺着 add （）方法看下去

[CLMan]

作为一个过来人，你犯了自学的通病：缺乏背景知识，然后钻牛角尖，后果是浪费大量时间成为了“计算机民科”。

一个学过数据结构与算法的人，除非他看了 PriorityQueue.toString()的文档说明，他根本不会调用`System.out.println(q1);`，因为在数据结构与算法里，堆实现的优先队列，其打印结果是未定义的。

很多喜欢吊"Java 源码袋子"的人也是这样，明明不懂，偏要分析来分析去搞得自己很懂的样子，就比如`java.util.concurrent`包，我敢说 99%的 Java 开发者都没看源码的必要。

正确的思路是跳出 Java 提供给你的封装，不补充该领域的专业知识，你这里就是“数据结构与算法”课程，再回头到具体的语言，看看其它语言是如何封装也是一个不错的思路。别一点领域知识都没有就去钻文档，钻源码，这样学习效率很低下，而且思维被 Java 的封装给局限了。

[CLMan]

@CLMan 更正“不补充该领域的专业知识”，应该为“补充该领域的专业知识”
更正“看看其它语言是如何封装也是一个不错的思路”，应该为“了解其它语言是如何封装也很有帮助”

[asssfsdfw]

....
1. q1 构建的是最小堆(自然序)，q2 构建的是最大堆
2. print 调的是 toString 方法，是按 collection 迭代的（内部迭代数组），不是按照堆有序打印的

[BQsummer]

13L 在说什么东西

[boatrain1111]

@CLMan #13 诚然 OP 犯了错，但你这妄自揣测别人也是挺搞笑的

[CLMan]

@boatrain1111 我作为一个过来者，认为他犯了初学者的毛病，指出来有什么问题？除此之外，我揣测了他什么？

[siweipancc]

多看看方法说明，给你个思路：for 调用是 iterator ，就跳遍历器那一节，能避免很多坑。
13 楼前半部分可以看，后半部分你可以忽略

[MeiJM]

优先级队列用的是数组实现的 2 叉堆，不保证数组顺序，只保证顶点最大 按排序内容实现的 compare 接口来。
可以看看这个博客，讲的还可以
https://www.cnblogs.com/henry-1202/p/9307927.html