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