PriorityQueueのComparatorについて

Question

LeetCodeでこの問題を解いています。→218. The Skyline Problem

この問題の解答例の一つとして以下のコードがあるのですが、PriorityQueueについて質問させてください。

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        Map<Integer, List<int[]>> cps = new TreeMap<>();
        for (int[] b : buildings) {

            cps.computeIfAbsent(b[0], (k) -> new ArrayList<int[]>()).add(b);
            cps.computeIfAbsent(b[1], (k) -> new ArrayList<int[]>()).add(b);
        }
        
     
        PriorityQueue<int[]> pq = new PriorityQueue<>((b2, b1) -> Integer.compare(b1[2], b2[2]));
        List<List<Integer>> ret = new ArrayList<>();
        for (Integer x : cps.keySet()) {
            for (int[] b : cps.get(x)) {
                if (x == b[0]) {
                    pq.add(b);
                } else {
                    pq.remove(b);
                }
            }
            if (pq.isEmpty()) {
                ret.add(Arrays.asList(x, 0));
            } else if (ret.isEmpty() || pq.peek()[2] != ret.get(ret.size() - 1).get(1)) {
                ret.add(Arrays.asList(x, pq.peek()[2]));
            }
        }
        return ret;
    }
}

こちらの部分に関して、

  PriorityQueue<int[]> pq = new PriorityQueue<>((b1, b2) -> Integer.compare(b2[2], b1[2]));

pqで追加された値の中で大きい値を.peekを実施したときに返していることはわかったのですが、なぜComparatorをこのように書くのでしょうか。
特に、(b1, b2)と(b2[2], b1[2]))でb1,b2の順番が逆なのはなぜなのでしょうか。
デバックしてみて(b2[2], b1[2])を(b1[2], b2[2]と逆にすると動かないのは確認したのですが、、、

Integer.compare を調べると

Integer.compare    
パラメータ:
x - 比較する最初のint
y - 比較する2番目のint
戻り値:
x == yの場合は値0、x < yの場合は0より小さい値、x> yの場合は0より大きい値
*/

という記述がありました。

つまり追加された値b2[2]とb1[2]を比較？して、0か-1か1かを返しているのと思うのですが、PriorityQueueが勝手にそのInteger.compareの戻り値に応じて新しく来た値を並べ替えている、ということでしょうか

Answer 1

つまり追加された値b2[2]とb1[2]を比較？して、0か-1か1かを返しているのと思うのですが、PriorityQueueが勝手にそのInteger.compareの戻り値に応じて新しく来た値を並べ替えている、ということでしょうか

ざっくりいうとそんな感じです。実際には「並び替える」必要は無く、peekなどで取り出す際に、最小の要素を探せればいいのです。
今回の場合、配列のインデックス2の要素（この問題でいうところのビルの高さ）が最大のものを「最小」とみなし、peekで取り出すことになります。
この「最大のものを『最小』とみなす」仕様を伝えるのが、PriorityQueueのコンストラクタでComparatorを渡すこの部分になります。

  PriorityQueue<int[]> pq = new PriorityQueue<>((b1, b2) -> Integer.compare(b2[2], b1[2]));

問題のComparatorの部分ですが、こう書けばわかるでしょうか？

  PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] b1, int[] b2) {
                return Integer.compare(b2[2], b1[2]));
            }
  });

Comments

[macaroni323]

理解できました。ありがとうございます。