[자료구조] 우선순위 큐 2 - 자바

숫자가 클 수록 우선순위가 높다는 문제에서 우선순위 큐를 내림차순으로 설정해서 사용하였다.

여기서 다음과 같은 이슈가 발생하였다.

우선순위 큐에 {3,7,6,2,4}를 넣었을 때 당연히 {7,6,4,3,2} 가 나올 줄 알았지만 {7,4,6,2,3}가 나왔다.

 

찾아보니 자바에서 우선순위 큐는 힙으로 구현되어있다는 것을 알았다. 이전에 정리했었는데..ㅎ 그래서 이번에는 제대로 이해하려고 한다.

[자료구조] 힙(Heep) & 우선순위 큐

---

자바에서 우선순위 큐는 아래와 같이 사용하며, reverseOrder()는 내림차순으로 정렬해주는 것이다.

PriorityQueue priority = new PriorityQueue<>(Collections.reverseOrder());

public static void main(String[] args) {
        PriorityQueue<Integer> priority = new PriorityQueue<>(Collections.reverseOrder());
        //{3,7,6,2,4}
        priority.add(3);
        priority.add(7);
        priority.add(6);
        priority.add(2);
        priority.add(4);

        for (int v : priority) {
            System.out.print(v + " "); // 7 4 6 2 3 -> 우선순위 큐는 힙으로 구현되어있음
        }
        while (!priority.isEmpty()) {
            System.out.print(priority.poll() + " "); // 7 6 4 3 2
        }

    }

 

위의 예시를 바탕으로 설명하자면 우선순위 큐에 {3,7,6,2,4}를 add 하면 내부적으로 데이터가 오른쪽과 같이 저장된다. 우선순위 큐에 내림차순으로 정렬하는 설정을 했기 때문에 최대 힙으로 구현되어있다.  

 

이 상태에서 전체 탐색을 하면 {7,6,4,3,2}이 나오게 된다.

 

하지만 poll을 하면 {7,6,4,3,2}이 나오게 된다. 그 이유는 최대 힙의 삭제 과정을 참고하면 이해하기 쉽다. 간단하게 설명하자면, 7이 poll 되는 순간 가장 아래의 3이 루트로 올라가게 되고, 최대 힙을 찾기 위해 재정렬 과정을 거친다. 따라서 실제 동작은 {7,6,4,3,2} 와 같이 한다.