[자료구조] 우선순위 큐(Priority Queue) 정리

1. 우선순위 큐(Priority Queue)란?

우선순위 큐란, 큐(Queue)에 입력된 데이터를 우선순위에 따라 먼저 처리하고 싶은 경우에 사용합니다. 따라서 기존 FIFO(First In First Out)를 따르는 큐와는 다르게 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나옵니다.

 

2. 우선순위 큐 구현방법

우선순위 큐를 구현하는 방법은 크게 2가지가 있습니다.

 

[1] 리스트(List)를 이용하여 구현하는 방법

[2] 힙(Heap)을 이용하여 구현하는 방법

2.1. 리스트를 이용하여 구현하는 방법

리스트(List)를 이용하여 구현하게 되면 매우 간단히 구현할 수 있는 장점이 있습니다. 하지만, 리스트를 이용하여 구현하는 경우, 자료의 입출력의 속도는 선형적이므로(앞에서 부터 찾아가는 방법) 자료가 매우 많아질 경우 느려질 수 있습니다.

2.2 힙(Heap)을 이용하여 구현하는 방법

힙(Heap)을 이용하여 구현하게 되면 리스트만큼 간단하게 구현하지는 못하지만, 리스트보다 자료의 입력과 출력이 훨씬 빠름을 보장합니다.

2.3. List VS Heap 

위의 두 방법의 자료의 입출력 속도를 비교하면 다음과 같습니다.

Priority Queue	자료 입력	자료 출력
List	O(1)	O(N)
Heap	O(logN)	O(logN)

 

N개의 자료를 모두 입력하고 출력하는 경우에 대해서, List는 O(N)의 속도를 보장하고 Heap의 경우에는 O(logN)의 속도를 보장합니다.

따라서 Heap을 이용하여 구현하였때의 속도가 더 빠름을 알 수 있습니다.

 

또한 Heap을 사용하여 구현하는 경우, 데이터를 모두 입력하게 되면 그 자체로도 정렬이 수행되는 장점이 있습니다.