Почему PriorityQueue работает неправильно?

Question

Вот мой код:

public static List<int[]> getSkyline(int[][] buildings) { 
    List<int[]> res = new ArrayList<>(); 

    PriorityQueue<int[]> heights = new PriorityQueue<>(buildings.length * 2, new Comparator<int[]>() { 
     @Override 
     public int compare(int[] o1, int[] o2) { 
      if (o1[0] == o2[0]) { 
       return o1[1] - o2[1]; 
      } else { 
       return o1[0] - o2[0]; 
      } 
     } 
    }); 

    for (int[] h : buildings) { 
     heights.add(new int[]{h[0], -h[2]}); 
     heights.add(new int[]{h[1], h[2]}); 
    } 


    for (int[] height : heights) { 
     System.out.println(Arrays.toString(height)); 
    } 

    return res; 
} 

public static void main(String[] args) { 
    getSkyline(new int[][]{{0, 2, 3}, {2, 5, 3}}); 

} 

В моей идее, так как вход new int[][]{{0, 2, 3}, {2, 5, 3}}, выход должен быть [0, -3][2, -3][2, 3][5, 3], но на самом деле это показывает [0, -3][2, 3][2, -3][5, 3]. Может ли кто-нибудь сказать мне, что не так в моем коде? Заранее спасибо.

Answer 1

Причина заключается в том, что PriorityQueue<T> не упорядочивает элементы на итерации:

Документация public Iterator<E> iterator() утверждает, что метод

Возвращает итератор над элементами в этой очереди. Итератор не возвращает элементы в каком-либо конкретном порядке.

Чтобы получить заказ, что вы ожидаете, что вам нужно удалить элементы из приоритетной очереди один за другим, и напечатать их:

while (heights.size() != 0) { 
    int[] height = heights.poll(); 
    System.out.println(Arrays.toString(height)); 
} 

Это изменение приводит следующий вывод:

[0, -3] 
[2, -3] 
[2, 3] 
[5, 3] 

Demo.