PriorityQueue 自定义排序

Question

我已经为我的节点优先级队列实现了自定义比较器，但由于某种原因它无法正常工作。任何帮助表示赞赏。如果我的节点 class 实现可比性，我也会得到相同的结果。

Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>()
{

        public int compare(Node node1, Node node2)
        {
            if (node1.getCost() < node2.getCost())
            {
                return -1;
            }
            else if (node1.getCost() < node2.getCost())
            {
                return 1;
            }

            return 0;
        }
});

    Node node1 = new Node(initState, null,0);
    node1.setCost(20);
    Node node2 = new Node(initState, null,0);
    node2.setCost(15);
    Node node3 = new Node(initState, null,0);
    node3.setCost(10);
    Node node4 = new Node(initState, null,0);
    node4.setCost(5);
    Node node5 = new Node(initState, null,0);
    node5.setCost(4);
    Node node6 = new Node(initState, null,0);
    node6.setCost(3);

    for (Node node : queue)
    {
        System.out.println(node.getCost());
    }

输出

3

5

4

20

10

15

Answer 1

您的比较器 class 有误。 "if" 和 "else if" 检查相同的条件。检查下面的更正版本。

new Comparator<Node>()
{

    public int compare(Node node1, Node node2)
    {
        if (node1.getCost() < node2.getCost())
        {
            return -1;
        }
        else if (node1.getCost() > node2.getCost())
        {
            return 1;
        }

        return 0;
    }
}

我假设你熟悉比较器的概念，上面是一个错字。如果不是这种情况，您也许可以 learn more on that here.

Answer 2

使用 "foreach" 浏览您的 collection 使用 PriorityQueue.iterator() 产生的 Iterator。

The javadoc of this method 提到

The iterator does not return the elements in any particular order.

您将不得不使用另一种方法来迭代您的 PriorityQueue。

以下应该有效：

while(!queue.isEmpty()) {
    Node currentNode = queue.poll();
    // ...
}

PriorityQueue 自定义排序

PriorityQueue custom sorting

java

priority-queue

comparator