[C++] Priority Queue - 우선순위 큐

오늘 공부해 볼 자료구조는 우선순위 큐이다.

 

우선순위 큐는 어디서 사용되는가?

- 시뮬레이션 시스템

- 네트워크 트래픽 제어

- 운영체제에서의 작업 스케쥴링

- 수치 해석적 계산

 

우선 큐(Queue)라는 자료구조는 FIFO(First In First Out) 구조로 먼저 들어온 데이터가 먼저 나오는 구조이다.

이와 달리 우선순위 큐는 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다. 보통 우선순위 큐는 힙(Heap)으로 구현된다. 

 

힙(Heap)

- 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조

- 여러 개의 값들 중에 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

- 힙은 중복 값을 허용함.'

 

힙의 종류

- 최대 힙 : 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리

- 최소 힙 : 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리

 

힙의 시간복잡도 = O(logN)

 

완전 이진 트리?

• 완전 이진 트리(完全二進-, 영어: complete binary tree)에서, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h 에서 1부터 2h-1 개의 노드를 가질 수 있다. 또 다른 정의는 가장 오른쪽의 잎 노드가 (아마도 모두) 제거된 포화 이진 트리다. 어떤 저술자는 완전(complete)라는 용어를 사용해 위에서 정의한 포화 이진 트리 대신, 이러한 종류의 트리를 거의 완전한(almost complete) 이진 트리 또는 대체로 완전한(nearly complete) 이진 트리라고 하는 경우도 있다. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

 

즉, 노드를 삽입할 때에 왼쪽부터 차례대로 노드를 추가하는 이진트리를 말한다.

완전 이진 트리의 예

우리는 우선순위 큐를 STL에서 사용할 수 있다.

 

#include <queue>

를 한 후에, priority_queue<>를 사용하면 된다. 간단하게 코드를 짜서 보는게 좋을 것 같다.

stl-priority queue 예제

다음과 같이 priority_queue를 less로 선언하면 최소힙, greater로 선언하면 최대힙 형태로 사용할 수 있다. 이렇게 해서 실행하면 다음과 같은 결과를 얻을 수 있다.

실행 결과

운영체제에서 이와 같은 우선순위 큐를 사용했을 때 나타나는 문제점이 있다. 바로 기아현상이다.

기아 현상은 프로세스가 계속해서 들어오는데, 우선순위가 낮은 순위의 프로세스가 높은 순위의 프로세스에 의해 계속해서 순서를 밀려서 실행되지 못하는 현상을 말한다. 그러므로 이런 기아 현상에 유의하여 사용해야 한다.