PriorityQueue 无法正常工作

Question

我做了一个优先级队列，它插入对象并将它们与成本参数进行比较，当两个成本相等时，它应该使它们保持排队顺序，但我在调试后发现有一次是排队顺序，另一次是排队顺序不符合顺序，但我没有发现我的代码有什么问题我找不到任何其他 post 帮助。

import java.util.*;
import java.lang.*;
import java.io.*;

class Node implements Comparable<Node>
{
    int x, y, dir;

    Node(int x, int y, int dir)
    {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }

    public int compareTo(Node o)
    {
        if (Ideone.cost[o.x][o.y] == Ideone.cost[x][y]) {
            return 1;
        } else {
            int d = Ideone.cost[x][y] - Ideone.cost[o.x][o.y];
            if (d > 0) {
                return 1;
            } else {
                return -1;
            }
        }
    }
}

class Ideone
{
    public static int[][] cost;
    static PriorityQueue<Node> p;

    public static void main(String[] args)
        throws Exception
    {
        p = new PriorityQueue<Node>();

        cost = new int[13][11];

        for (int[] row : cost)
            Arrays.fill(row, -1);

        cost[0][8]  = 366564;
        cost[2][9]  = 368282;
        cost[1][3]  = 368282;
        cost[4][9]  = 368282;
        cost[0][9]  = 376564;
        cost[1][9]  = 372423;
        cost[5][9]  = 372423;
        cost[0][3]  = 436564;
        cost[7][0]  = 378282;
        cost[2][10] = 378282;
        cost[4][10] = 378282;
        cost[0][4]  = 382423;
        p.add(new Node(0, 8, 8));
        p.add(new Node(2, 9, 8));
        p.add(new Node(1, 3, 7));
        p.add(new Node(4, 9, 2));
        p.add(new Node(0, 9, 8));
        p.add(new Node(1, 9, 8));
        p.add(new Node(5, 9, 2));
        p.add(new Node(0, 3, 6));
        p.add(new Node(7, 0, 3));
        p.add(new Node(2, 10, 8));
        p.add(new Node(4, 10, 2));
        p.add(new Node(0, 4, 7));

        while (p.size() != 0) {
            Node n1 = p.poll();
            System.out.println(n1.x + " " + n1.y + " " + cost[n1.x][n1.y]);
        }
    }
}

输出是

0 8 366564
1 3 368282
2 9 368282
4 9 368282
5 9 372423
1 9 372423
0 9 376564
4 10 378282
2 10 378282
7 0 378282
0 4 382423
0 3 436564

但我期待：

0 8 366564
2 9 368282
1 3 368282
4 9 368282
1 9 372423
5 9 372423
0 9 376564
7 0 378282
2 10 378282
4 10 378282
0 4 382423
0 3 436564

Answer 1

您需要——确实如此——遵循 Peter Lawrey 的建议并将插入顺序存储在您插入优先级队列的每个节点中。用代码更容易解释。您的节点 class 可能会变成：

class Node implements Comparable<Node>
{
    int x, y, dir;
    /** the order in which the node was inserted into the priority queue (if it was) */
    int insertionOrder;

    Node(int x, int y, int dir, int insertionOrder)
    {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.insertionOrder = insertionOrder;
    }

    public int compareTo(Node o)
    {
        int d = Ideone.cost[x][y] - Ideone.cost[o.x][o.y];
        if (d == 0) {
            // keep insertion order
            return insertionOrder - o.insertionOrder;
        } else {
            return d;
        }
    }
}

还有你的主要方法：

public static void main(String[] args)
{
    p = new PriorityQueue<Node>();
    int numInserted = 0;

    cost = new int[13][11];

    for (int[] row : cost)
        Arrays.fill(row, -1);

    cost[0][8]  = 366564;
    cost[2][9]  = 368282;
    cost[1][3]  = 368282;
    cost[4][9]  = 368282;
    cost[0][9]  = 376564;
    cost[1][9]  = 372423;
    cost[5][9]  = 372423;
    cost[0][3]  = 436564;
    cost[7][0]  = 378282;
    cost[2][10] = 378282;
    cost[4][10] = 378282;
    cost[0][4]  = 382423;
    p.add(new Node(0, 8, 8, numInserted));
    numInserted++;
    p.add(new Node(2, 9, 8, numInserted));
    numInserted++;
    p.add(new Node(1, 3, 7, numInserted));
    numInserted++;
    p.add(new Node(4, 9, 2, numInserted));
    numInserted++;
    p.add(new Node(0, 9, 8, numInserted));
    numInserted++;
    p.add(new Node(1, 9, 8, numInserted));
    numInserted++;
    p.add(new Node(5, 9, 2, numInserted));
    numInserted++;
    p.add(new Node(0, 3, 6, numInserted));
    numInserted++;
    p.add(new Node(7, 0, 3, numInserted));
    numInserted++;
    p.add(new Node(2, 10, 8, numInserted));
    numInserted++;
    p.add(new Node(4, 10, 2, numInserted));
    numInserted++;
    p.add(new Node(0, 4, 7, numInserted));
    numInserted++;

    while (p.size() != 0) {
        Node n1 = p.poll();
        System.out.println(n1.x + " " + n1.y + " " + cost[n1.x][n1.y]);
    }
}

以上主要方法打印：

0 8 366564
2 9 368282
1 3 368282
4 9 368282
1 9 372423
5 9 372423
0 9 376564
7 0 378282
2 10 378282
4 10 378282
0 4 382423
0 3 436564

我相信这是您所期望的。

Answer 2

A PriorityQueue uses a BinaryHeap 对其元素进行排序。这意味着不能保证每个元素在插入时都会与其他元素进行比较（因此保留相等元素的添加顺序）。为了保留相同元素的加法顺序，您需要在元素之间进行另一次比较。一种可能的方法是为每个节点使用时间戳

class Node implements Comparable<Node>
{
    int x, y, dir;
    Long timestamp = System.nanoTime();

    Node(int x, int y, int dir)
    {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }

    public int compareTo(Node o){

        if (Ideone.cost[o.x][o.y] == Ideone.cost[x][y]) {
            return timestamp.compareTo(o.timestamp);
        }else {
            int d = Ideone.cost[x][y] - Ideone.cost[o.x][o.y];
            if (d > 0) {
                return 1;
            } else {
                return -1;
            }
        }
    }  
}

如果涉及多线程，这会有缺点，在这种情况下，您需要存储加法顺序并使用该值进行比较

class Node implements Comparable<Node>
{
    int x, y, dir, pos;

    Node(int x, int y, int dir, int pos)
    {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.pos = pos;
    }

    public int compareTo(Node o){

        if (Ideone.cost[o.x][o.y] == Ideone.cost[x][y]) {
            Integer p1 = pos;
            return p1.compareTo(o.pos);
        }else {
            int d = Ideone.cost[x][y] - Ideone.cost[o.x][o.y];
            if (d > 0) {
                return 1;
            } else {
                return -1;
            }
        }
    }  
}

//then to add
p.add(new Node(0, 8, 8, p.size()));

当然，如果项目的删除和添加是交错的，后一种方法有缺点（在这种情况下，您将需要一个单独的变量来保持插入的增量）

int additionValue = 0;
p.add(new Node(0, 8, 8, additionValue++));

PriorityQueue 无法正常工作

PriorityQueue not working properly

java

priority-queue