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