Java 优先队列问题

查看 165|回复 14
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 key = (Comparable) 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 更正“不补充该领域的专业知识”,应该为“补充该领域的专业知识”
更正“看看其它语言是如何封装也是一个不错的思路”,应该为“了解其它语言是如何封装也很有帮助”
您需要登录后才可以回帖 登录 | 立即注册

返回顶部