V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yuanyuandeqiu
V2EX  ›  Java

Java 优先队列问题

  •  
  •   yuanyuandeqiu · 2023-06-07 15:58:59 +08:00 · 1947 次点击
    这是一个创建于 404 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这样一段程序:

    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]
    }

    请教各位,为什么会排序错误
    20 条回复    2023-06-14 18:12:16 +08:00
    Zakl21
        1
    Zakl21  
       2023-06-07 16:02:54 +08:00
    直接 print 不一定有序的,你试试 while true pop 打印
    Nazz
        2
    Nazz  
       2023-06-07 16:05:09 +08:00
    正确的姿势是:

    while(q.len() >0) {
    println(q.pop())
    }
    yuanyuandeqiu
        3
    yuanyuandeqiu  
    OP
       2023-06-07 16:08:09 +08:00
    @Nazz
    @Zakl21
    感谢,那 debug 的时候是不是也是无序的
    yuanyuandeqiu
        4
    yuanyuandeqiu  
    OP
       2023-06-07 16:13:59 +08:00
    debug 的时候 q 的顺序和 System.out.println 打印出来的一致,这是为什么
    Nazz
        5
    Nazz  
       2023-06-07 16:33:56 +08:00
    好好看看数据结构基础吧
    jamezee
        6
    jamezee  
       2023-06-07 16:37:04 +08:00
    看下类的注释就知道了
    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
        7
    yuanyuandeqiu  
    OP
       2023-06-07 16:44:07 +08:00
    @Nazz
    @jamezee
    感谢
    fengpan567
        8
    fengpan567  
       2023-06-07 16:45:37 +08:00
    while(q2.peek() != null) {
    println(q.poll());
    }
    azusachino
        9
    azusachino  
       2023-06-07 16:48:14 +08:00
    优先队列只保证最大 /小堆,不保证顺序; online challenge 挂了之后,一查才知道。。。
    Koril
        10
    Koril  
       2023-06-07 17:07:06 +08:00
    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
        11
    nerkeler  
       2023-06-07 17:53:16 +08:00
    [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
        12
    nerkeler  
       2023-06-07 17:55:49 +08:00
    看错了,是这一段
    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
        13
    CLMan  
       2023-06-07 21:33:19 +08:00
    作为一个过来人,你犯了自学的通病:缺乏背景知识,然后钻牛角尖,后果是浪费大量时间成为了“计算机民科”。

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

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

    正确的思路是跳出 Java 提供给你的封装,不补充该领域的专业知识,你这里就是“数据结构与算法”课程,再回头到具体的语言,看看其它语言是如何封装也是一个不错的思路。别一点领域知识都没有就去钻文档,钻源码,这样学习效率很低下,而且思维被 Java 的封装给局限了。
    CLMan
        14
    CLMan  
       2023-06-07 21:35:32 +08:00
    @CLMan 更正“不补充该领域的专业知识”,应该为“补充该领域的专业知识”
    更正“看看其它语言是如何封装也是一个不错的思路”,应该为“了解其它语言是如何封装也很有帮助”
    asssfsdfw
        15
    asssfsdfw  
       2023-06-08 09:01:24 +08:00
    ....
    1. q1 构建的是最小堆(自然序),q2 构建的是最大堆
    2. print 调的是 toString 方法,是按 collection 迭代的(内部迭代数组),不是按照堆有序打印的
    BQsummer
        16
    BQsummer  
       2023-06-08 10:23:23 +08:00
    13L 在说什么东西
    boatrain1111
        17
    boatrain1111  
       2023-06-08 11:05:28 +08:00
    @CLMan #13 诚然 OP 犯了错,但你这妄自揣测别人也是挺搞笑的
    CLMan
        18
    CLMan  
       2023-06-08 12:19:40 +08:00
    @boatrain1111 我作为一个过来者,认为他犯了初学者的毛病,指出来有什么问题?除此之外,我揣测了他什么?
    siweipancc
        19
    siweipancc  
       2023-06-08 12:35:27 +08:00 via iPhone
    多看看方法说明,给你个思路:for 调用是 iterator ,就跳遍历器那一节,能避免很多坑。
    13 楼前半部分可以看,后半部分你可以忽略
    MeiJM
        20
    MeiJM  
       2023-06-14 18:12:16 +08:00
    优先级队列用的是数组实现的 2 叉堆,不保证数组顺序,只保证顶点最大 按排序内容实现的 compare 接口来。
    可以看看这个博客,讲的还可以
    https://www.cnblogs.com/henry-1202/p/9307927.html
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   948 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 21:13 · PVG 05:13 · LAX 14:13 · JFK 17:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.