时间戳

首页 > 解决方案 > Java中优先级队列中的自定义比较器

java - Java中优先级队列中的自定义比较器

问题描述

我正在尝试将优先级队列与自定义比较器一起使用，但是我无法实现预期的功能。：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestMain {

    public static void main(String[] args) {
        Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            public int compare(Node a, Node b) {
                if(a.level == b.level) {
                    return a.data - b.data;
                }
                return a.level - b.level;
            }
        });
        
        queue.add(new Node(0,1));
        queue.add(new Node(1,2));
        queue.add(new Node(1,4));
        queue.add(new Node(2,3));
        queue.add(new Node(2,7));
        queue.add(new Node(2,2));
        queue.add(new Node(2,5));
        
        System.out.println(queue);
    }
    
    private static class Node {
        int level;
        int data;
        
        Node(int level, int data) {
            this.level = level;
            this.data = data;
        }
        
        public String toString() {
            return level + ":" + data;
        }
    }
}

预期产出 =[0:1, 1:2, 1:4, 2:2, 2:3, 2:5, 2:7] 实际产出 =[0:1, 1:2, 1:4, 2:3, 2:7, 2:2, 2:5]

我希望优先级队列中的元素首先按级别排序，然后按数据排序。

标签： javacomparator

解决方案

toString 方法可能不会按检索顺序显示元素。因此，这并不意味着您的比较器不正确。

以下是在PriorityQueu 的 javadoc中编写的（重点是我的）：

此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选方法。方法 iterator() 中提供的 Iterator 和方法 spliterator() 中提供的 Spliterator 不能保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用 Arrays.sort(pq.toArray())。

这里没有明确写出来，但是 toString 依赖于迭代器，因此元素也可能不会以预期的方式显示。toString 方法是在类 Collection 中定义的，这里没有特别重写。

PriorityQueu 可能是使用数组中的二进制堆实现的。从那里，很自然地，迭代是按数组顺序进行的。以正确的顺序显示元素需要将它们从队列中删除，因此除了在其他地方排序副本之外是不可能的，这对于简单的 toString 来说太重了。

推荐阅读