우선순위 큐

 우선순위 큐는 우선 순위의 개념을 큐에 도입한 자료구조이다. 보통의 큐는 선입선출(FIFO) 의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐(priority queue) 에서는 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐를 스택이나 큐와 비교해보면 스택에서는 먼저 들어간 데이터가 가장 늦게 나오게 된다. 큐에서는 가장 먼저 들어간 데이터가 가장 먼저 나오게 된다. 우선순위 큐는 사실 가장 일반적인 큐라고 할 수 있는데 왜냐하면 스택이나 큐도 우선순위 큐를 사용하여 얼마든지 구현할 수 있기 때문이다. 즉 적절한 우선 순위만 부여하면 우선순위 큐는 스택이나 큐로 동작할 것이다. 예를 들어 데이터가 들어온 시각을 우선 순위로 잡으면 일반적인 큐처럼 동작할 것이다. 

 

우선순위 큐 추상자료형(ADT)
- 객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
- 연산 : 
create() ::=우선순위 큐를 생성한다
init(q) ::= 우선순위 큐 q를 초기화한다
is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사한다
is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사한다
insert(q, x) ::= 유선순위 큐 q에 요소 x를 추가한다
delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다
find(q) ::= 우선순위가 가장 높은 요소를 반환한다

우선순위 큐는 0개 이상의 요소의 모임이다. 각 요소들은 우선 순위값을 가지고 있다. 가장 중요한 연산은 insert, delete 연산이다. 우선순위 큐는 2가지로 구분할 수 있는데 최소 우선순위 큐는 가장 우선 순위가 낮은 요소를 먼저 삭제한다. 최대 우선순위 큐는 반대로 가장 우선 순위가 높은 요소가 먼저 삭제된다. 

 

• 우선순위 큐의 구현 방법

• 배열을 사용하는 방법

먼저 정렬이 되어있지 않은 배열을 사용하는 경우를 분석해보자. 정렬이 안 된 배열을 사용하게 되면 삽입은 가장 간단하다. 그냥 배열의 맨 끝에 새로운 요소를 추가하면 된다. 따라서 삽입의 시간 복잡도는 O(1)이다. 그러나 삭제를 할 때는 가장 우선 순위가 높은 요소를 찾아야 한다. 정렬이 안 되어 있으므로 처음부터 끝까지 모든 요소들을 스캔하여야 한다. 따라서 삭제의 복잡도는 O(n) 이 된다. 그리고 요소가 삭제된 다음, 뒤에 있는 요소들을 앞으로 이동시켜야 하는 부담도 있다. 이번에는 정렬이 되어 있는 배열의 경우를 생각해보자. 새로운 요소를 삽입할 때에는 다른 요소와 값을 비교하여 적절한 삽입 위치를 결정하여야 한다. 삽입 위치를 찾기 위하여 순차탐색이나 이진탐색과 같은 방법을 이용할 수 있다. 삽입 위치를 찾은 다음에는 삽입 위치 뒤에 있는 요소들을 이동시켜서 빈자리를 만든 다음, 삽입해야 한다. 따라서 삽입시의 시간복잡도는 일반적으로 O(n)이다. 그 대신 삭제 시에는 간단하다. 숫자가 높은 것이 우선 순위가 높다고 가정하면 맨 뒤에 위치한 요소를 삭제하면 된다. 이 경우 삭제의 시간 복잡도는 O(1) 이 될 것이다.

 

 

 

• 연결 리스트를 사용하는 방법

연결 리스트를 이용하는 방법도 배열의 경우와 크게 다르지 않다. 정렬된 상태로 연결 리스트를 유지할 수도 있고 정렬이 안 된 채로 연결 리스트를 사용할 수 있다. 정렬이 안 된 리스트라면 삽입 시에는 첫 번째 노드로 삽입시키는 것이 유리하다. 또한 삽입 시에 배열과 달리 다른 노드를 이동할 필요가 없다. 포인터만 변경하면 된다. 따라서 삽입의 시간 복잡도는 O(1) 이다. 삭제 시에는 포인터를 따라서 모든 노드를 뒤져보아야 한다. 이 경우 시간 복잡도는 O(n) 이 될 것이다. 만약 연결 리스트를 정렬시킨 상태로 사용한다면 시간 복잡도는 어떻게 될까? 이 경우에는 우선 순위가 높은 요소가 앞에 위치하는 것이 유리하다. 따라서 우선순위가 높은 요소가 첫 번째 노드가 되도록 한다. 삽입시에는 우선 순위값을 기준으로 삽입위치를 찾아야 하므로 O(n) 이 된다. 삭제 시에는 첫 번째 노드를 삭제하면 되므로 O(1) 이다.

 

• 히프를 사용하는 방법

히프(heap) 는 완전 이진 트리의 일종으로 우선순위 큐를 위하여 특별히 만들어진 자료 구조이다. 이프는 일종의 느슨한 정렬 상태를 유지한다. 즉 완전히 정렬된 것은 아니지만 전혀 정렬이 안된 것도 아닌 상태를 유지한다. 히프는 이러한 느슨한 정렬 상태를 이용하여 우선순위 큐를 구현한다.