Comportamento estranho do comparador PriorityQueue quando a ordem de classificação é obtida do hashmap

Enquanto trabalhava no LeetCode 675 , me deparei com um comportamento estranho PriorityQueue Comparatorque não consigo explicar.

Para resumir, vou apresentar a essência da declaração do problema; os interessados ​​podem lê-la em detalhes no LeetCode.

Dada uma matriz mxn chamada forest, algumas células são designadas como trees. O desafio é encontrar o número mínimo de passos para visitar (cortar) todas as células da árvore, em ordem crescente de altura da árvore.

Para resolver isso, encontro todas as árvores e as ordeno em ordem crescente de altura. Em seguida, calculo a distância mínima de cada árvore até a próxima executando uma busca A* usando a função heurística:distance from source + Manhattan distance from the goal

O número mínimo de passos para cortar todas as árvores é a soma de todas as distâncias A*. Se em algum momento a busca A* não retornar um caminho, eu aborto.

class Solution {
  private final int[][] dx = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

  public int cutOffTree(List<List<Integer>> forest) {
    int[] curr = new int[] {0, 0};
    int dist = 0;

    for (int[] next : getTreesSortedByHeight(forest)) {
      int d = minDist(forest, curr, next);
      if (d < 0) {
        return -1;
      }
      curr = next;
      dist += d;
    }

    return dist;
  }

  private List<int[]> getTreesSortedByHeight(List<List<Integer>> forest) {
    List<int[]> trees = new ArrayList<>();
    for (int row = 0; row < forest.size(); row++) {
      for (int col = 0; col < forest.get(0).size(); col++) {
        if (forest.get(row).get(col) > 1) {
          trees.add(new int[] {row, col});
        }
      }
    }
    trees.sort(Comparator.comparingInt(a -> forest.get(a[0]).get(a[1])));
    return trees;
  }

  int minDist(List<List<Integer>> forest, int[] start, int[] goal) {
    int m = forest.size();
    int n = forest.get(0).size();
    Map<Integer, Integer> costs = new HashMap<>();
    costs.put(start[0] * n + start[1], manhattanDist(start[0], start[1], goal));
    // GOTCHA: Fetching the distance from the cost map using the coordinates doesn't work!
    Queue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    heap.offer(new int[] {0, 0, start[0], start[1]}); // [cost, distance, row, column]

    while (!heap.isEmpty()) {
      int[] curr = heap.poll();
      int dist = curr[1];
      int row = curr[2];
      int col = curr[3];

      if (row == goal[0] && col == goal[1]) {
        return dist;
      }
      for (int[] d : dx) {
        int r = row + d[0];
        int c = col + d[1];
        if (r >= 0 && r < m && c >= 0 && c < n && forest.get(r).get(c) > 0) {
          int cost = dist + 1 + manhattanDist(r, c, goal);
          if (cost < costs.getOrDefault(r * n + c, Integer.MAX_VALUE)) {
            costs.put(r * n + c, cost);
            heap.offer(new int[] {cost, dist + 1, r, c});
          }
        }
      }
    }
    return -1;
  }

  private int manhattanDist(int row, int col, int[] goal) {
    return Math.abs(goal[0] - row) + Math.abs(goal[1] - col);
  }
}

Observe que cada entrada de heap contém o custo heurístico . Logicamente, isso é desnecessário , pois a entrada também contém as coordenadas da célula (linha e coluna), com as quais podemos obter a distância do costsmapa da seguinte maneira:

Queue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> costs.get(a[1] * n + a[2]);

• Na ausência do custo, a entrada do heap consiste em [distância, linha, coluna].

Mas isso não funciona e falha em um dos casos de teste. O caso de teste é enorme, então não vejo sentido em colá-lo aqui, pois é improvável que alguém tenha tempo para depurá-lo.

O que eu gostaria de saber é o porquê dessa estranheza.

Editar: código completo adicionado conforme solicitado em um comentário.