[230923] Java PriorityQueue와 Comparator 사용하기

PriorityQueue 사용

💬 알고리즘 문제에서 저장한 데이터를 우선순위에 따라 추출해야 했습니다. 이 경우 가장 먼저 떠오르는 것이 우선순위 큐(Heap)였습니다. Java에서 제공하는 자료구조였기에 쉽게 적용해 볼 수 있었습니다.

 

✔ 메커니즘

💬 Java에서 제공하는 PriorityQueue는 Comparator를 지정하지 않으면 제너릭에 입력한 타입의 Comparator 가져다가 씁니다. 이번에는 Integer를 사용했기 때문에 숫자의 크기에 따라 우선순위가 정해졌습니다. 

 

✔ 절댓값 크기로 우선순위 정하기

💬 문제에서 절댓값 크기와 절댓값이 같은 경우 숫자의 크기로 우선순위가 정해져야 했습니다. Integer Comparator를 사용하면 원하는 우선순위를 얻을 수 없습니다. 별도의 Comparator를 정의해야 했으며, 이를 위해 어떻게 동작하는지 파악할 필요가 있었습니다.

 

✔ PriorityQueue 우선순위가 정해지는 메커니즘

💬 Comparator를 정의해 주는 경우 내부적으로 siftUpUsingComprator 메서드에서 우선순위 기반으로 데이터를 저장합니다. 우선순위 큐는 부모 노드가 자식 노드보다 우선순위가 높기 때문에 부모와 자식 노드의 비교를 통해 데이터의 위치를 정할 수 있습니다. 여기서 우선순위가 높은 지를 체크하는 부분은 "cmp.compare(x, (T) e) >= 0"이었습니다. 두 값을 비교했을 때 음수 값이 나와야 새로운 데이터가 우선순위가 높다고 판단을 하고 있었습니다.

private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = x;
}​

 

✔ Comparator 적용

💬 위 로직 확인을 통해 우선순위를 높게 하려면 비교했을 때 음수 값이 나와야 한다는 것을 알았습니다. 이를 기반으로 코드를 작성해 보면 아래와 같습니다.
    ➡ 절댓값이 작을 경우 우선순위가 더 높다.
    ➡ 절댓값이 같은 경우 실제 값이 작은 경우 우선순위가 더 높다.  

Queue queue = new PriorityQueue<Integer>((Integer a, Integer b) -> compare(a,b));

public static int compare(Integer first, Integer second) {
    if(abs(first) == abs(second)) {
        return first < second ? -1 : 1;
    }

    return abs(first) < abs(second) ? -1 : 1;
}​