우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

우선순위 큐는 일반적인 큐의 FIFO(First-In First-Out) 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식을 선택한다.

예를들어, 6,7,3,2 순으로 Enqueue했을 때 2,3,6,7 순서대로 빠져나오는 경우를 들 수 있다.

우선순위 큐는 대표적으로 우선순위가 높은 작업을 먼저 큐에서 꺼내어 CPU를 할당하여 실행하게 하는 운영체제의 CPU 스케줄러에서 활용된다.

두 가지 방식

간단하게 생각해보면 우선순위 큐는 다음과 같이 서로 다른 두 가지 방식으로 구현이 가능하다.

• Enqueue할 때 우선순위 순서를 유지하도록(즉, 데이터를 enqueue할 때 우선순위가 유지되도록 공간에 데이터를 끼워넣는다고 생각하면 된다.)

• Dequeue할 때 우선순위 높은 것을 선택(즉, 큐에 들어가 있을 때에는 아무 순서로 들어가 있어도 상관없지만, dequeue할 때 가장 우선순위가 높은 것을 선택하도록 하는 것이라고 생각하면 된다.)

사실 이 두 가지 중 첫 번째의 구현 방식이 더 유리하다. 왜냐하면 첫 번째의 경우, 큐의 길이가 길어지더라도 enqueue할 때 모든 데이터 원소를 다 확인해볼 필요가 없기 때문이다. 반면 두 번째의 경우, dequeue할 때 우선순위가 가장 높은 것을 선택하려면 모든 데이터에 대하여 다 살펴보아야 하기 때문에 비효율적이다.

두 가지 재료

또한, 우선순위 큐는 선형 배열과 연결 리스트의 두 가지 재료를 이용하여 만들 수 있다.

시간적으로는 선형 배열보다는 연결 리스트를 이용하는 것이 좋다. 중간에 삽입해야 할 경우, 중간에서 링크를 끊고 삽입하여 다시 양쪽을 연결해줄 수 있는 연결 리스트가 시간적으로 더 유리하기 때문이다.

공간소요의 입장에서는 선형 배열이 공간을 덜 차지하므로 선형 배열이 유리하다.

일반적으로는 시간적으로 유리한 방식을 선택하는 경우가 많으므로, 보통 연결 리스트를 활용하여 우선순위 큐를 만든다.