PriorityQueue无法正常工作

Question

我已经创建了一个优先级队列，它插入对象并将它们与成本参数进行比较，当两个成本相等时它应该保持排队顺序，但是我在调​​试一次后发现它已排入队列中，时间不是这样的顺序，但我没有得到我的代码有什么问题我找不到任何其他职位帮助。

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

你所需要的 - 为需要 - 遵循从彼得Lawrey的建议和插入顺序存储在每个节点您插入优先队列。在代码中解释更容易。你的节点类将变成：

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使用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++));