[자료구조] Priority Queue

정의

Queue는 각 요소들 간의 우선순위(Priority)가 없이 FIFO(First In First Out, 선입선출법) 방식으로 데이터를 처리하였다. 반면, Priority Queue의 모든 요소는 <Key, Value>로 이루어져 있다. 그리고 이 Key가 요소들 간의 우선순위를 결정한다. 

 

가령, Priority(Key)의 값이 낮을수록 더 높은 우선순위를 부여한다고 가정하자. 

{<1,A>, <2,B>, <3,C>, <4,D>} 와 같은 Priority Queue가 있을 때, remove 연산을 수행하면 가장 Key 값이 낮은 <1,A>가 Priority Queue에서 제거되고, {<2,B>, <3,C>, <4,D>}가 되는 방식이다. 

 

구현

Priority Queue를 구현하는 방식에는 다음 두 가지가 있다.

1. Unsorted List로 구현

2. Sorted List로 구현

 

위 두 가지 방식 중 어떤 방식을 사용하느냐에 따라 insertion/removal 연산 간 trade-off가 발생한다.

 

먼저, Unsorted List로 Priority Queue를 구현하는 경우, 새로운 요소를 추가할 때는 그냥 list에 맨 뒤에 붙이면 되므로 time complexity가 O(1)인 반면, Priority Queue에서 제거할 요소를 찾을 때는 가장 우선순위가 높은 Key 값을 찾기 위해 전체 요소들을 한 번 순환해야 하므로 time complexity가 O(n)이 된다.

 

반면, Sorted List로 Priority Queue를 구현하는 경우, 새 요소를 추가할 때는 해당 요소의 Key 값에 따라 해당 요소가 삽입될 위치를 특정해야 하므로 time complexity가 O(n)이 된다. 반면, Priority Queue에서 제거할 요소를 찾을 때는 이미 요소들이 크기에 따라 정렬되어 있기 때문에 바로 priority가 가장 높은 요소를 찾을 수 있으므로 time complexity가 O(1)이 된다.

 

응용

"우선순위가 높은 요소를 먼저 반환한다"는 Priority Queue의 특징을 이용하여 Sorting에 Priority Queue를 활용할 수 있다.

 

가령, {2, 3, 4, 1}이라는 unsorted list가 있다고 하자. 각 요소들의 값을 key로 생각하고, 이를 Priority Queue에 넣는다.

 

{<2,->, <3,->, <4,->, <1,->} (unsorted list를 이용한 Priority Queue 가정)

 

그리고 이를 다시 하나씩 제거하면, Key가 작은 순서대로 나오기 때문에 결과적으로 list가 순서대로 정렬된다.

 

{1, 2, 3, 4}