알고리즘 - 우선순위 큐

우선순위 큐(Priority Queue)

---

우선순위 큐는 우선순위에 따라 값을 정렬하는 큐의 유형이다. 

 

우선순위 큐 생성하기

PriorityQueue<Integer> queue = new PriorityQueue<>();
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue를 생성하는 것을 살펴보면 두 가지 경우가 있다.

첫 번째로 우선순위 큐를 기본으로 생성하게 되면 우선순위가 낮은 값이 Queue의 맨 앞에 위치하게 된다.

두 번째로 Collections 클래스에 reverseOrder() 메서드를 사용하면 우선순위가 높은 값부터 맨 앞에 위치하게 된다는 차이가 있다.

 

우선순위 큐에 데이터 삽입하기

queue.add(1);
queue.add(3);
queue.add(7);
queue.add(2);
queue.add(5);
queue.add(6);

우선순위 큐는 일반적인 큐와 데이터를 삽입했을 때 위치가 달라진다.

그림으로 살펴보면서 우선순위 큐에서 데이터가 삽입될 경우 어떻게 위치하게 되는지 살펴보자

처음에 add(1), add(3), add(7)을 하면 위의 그림과 같이 트리 형태로 데이터가 삽입된다.

데이터는 우선순위가 낮은 것이 왼쪽부터 차례대로 들어가게 되는 것을 알아두면 좋을 것 같다.

 

그다음으로 add(2)와 add(5)를 하게 되는데 여기서 2의 값이 3보다 우선순위가 낮기 때문에 swap이 발생하게 되고 2와 3의 위치가 바뀌게 된다.

 

마지막으로 add(6)을 하게 되면 7보다 우선순위가 낮기 때문에 swap이 발생하고 6과 7의 위치가 바뀌게 된다.

이렇게 저장된 우선순위 큐를 출력해 보면 루트 노드인 1부터 시작하여 왼쪽에 위치한 값 먼저 출력하게 된다.

 

reverseOrder()를 적용한 우선순위 큐는 앞서 설명했던 것을 반대로 생각해 보면 될 것 같다.

우선순위를 가지고 정렬해 주는 것 외에는 일반적인 Queue와 같기 때문에 Queue가 가지고 있는 메서드를 사용하면 될 것 같다.