도입

이전에 다뤘던 큐의 핵심 연산 두 가지는 다음과 같았다.

• enqueue : 큐에 데이터를 삽입하는 행위
• dequeue : 큐에서 데이터를 꺼내는 행위

이와 마찬가지로 우선순위 큐의 핵심 연산 두 가지도 다음과 같다.

• enqueue : 우선순위 큐에 데이터를 삽입하는 행위
• dequeue : 우선순위 큐에서 데이터를 꺼내는 행위

하지만 연산 결과에서 차이가 있다.

큐는 먼저 들어간 데이터가 먼저 나오는 선입선출의 특징을 가지고 있었지만, 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다는 특징을 가지고 있다.

큐를 흔히 줄서기에 비유하는 것처럼, 우선순위 큐는 응급실에 비유할 수 있다. 응급실에서는 온 순서와 상관 없이 우선순위가 높은 환자가 먼저 치료를 받는다. 들어오는 순서와 나가는 순서가 상관이 없는 특징이 우선순위 큐와 비슷하다.

우선순위 큐의 구현

우선순위 큐는 다음과 같이 세 가지 방법으로 구현할 수 있다.

• 배열을 기반으로 구현하는 방법
• 연결 리스트를 기반으로 구현하는 방법
• 힙(heap)을 이용하는 방법

일반적으로 힙을 이용하는 방법을 사용한다.

그 이유는 다음과 같다.

우선순위 큐를 구현할 때 배열과 연결 리스트를 사용하지 않는 이유

배열

배열을 이용해서 우선순위 큐를 구현하게 된다면, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시키면 된다.

하지만 배열의 특성 상 데이터를 삽입, 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 앞으로 당기는 연산을 수행해야 하기 때문에 비효율적이다.

또한 삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

이러한 두 가지 이유 때문에 일반적으로 배열을 이용해서 우선순위 큐를 구현하지 않는다.

하지만 우선순위 큐를 구현하는 과정에서 배열을 완전히 쓰지 않는 것은 아니다. 우선순위 큐를 구현하기 위해 힙을 사용하는데 힙을 구현할 때 배열이 사용되기 때문이다. 배열을 순수하게 사용하진 않고, 배열을 이용해서 힙을 구현하고 그 힙으로 우선순위 큐를 구현한다고 보면 된다.

연결 리스트

연결 리스트를 이용해 우선순위 큐를 구현한다면 배열의 두 가지 단점 중 삽입, 삭제 과정에서 데이터를 한 칸씩 밀거나 당기는 연산을 수행해야 한다는 단점이 사라지게 된다.

하지만 여전히 삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 삽입하려는 데이터의 우선순위를 비교해야 할 수도 있다는 단점이 존재한다.

연결 리스트도 이러한 단점 때문에 우선순위 큐를 구현하기 적합한 자료구조가 아니다.

힙(Heap)

힙이란 이진 트리이되 완전 이진 트리이고, 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 작아야 하는 자료구조이다. 즉 루트 노드에 저장된 값이 가장 크거나 작아야 한다. 루트 노드의 값이 가장 큰 경우를 최대 힙(max heap), 루트 노드의 값이 가장 작은 경우를 최소 힙(min heap)이라고 한다.

이처럼 힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있기 때문에 우선순위 큐를 구현할 수 있는 자료구조이다.

힙에서의 데이터 저장 과정

트리의 맨 아래 레벨의 빈 공간 중 이진 트리 구조를 유지하는 가장 왼쪽의 위치에 우선 넣고자 하는 데이터를 저장한다. 새로운 데이터의 우선순위가 가장 낮다고 가정하는 것이다.

이후에 부모 노드와 우선순위를 비교한다. 만약 부모 노드의 우선 순위가 더 낮다면 위치를 서로 바꾼다.

부모 노드의 우선 순위가 더 높을 때까지 비교와 교환을 반복한다.

힙에서의 데이터 삭제 과정

힙에서 루트 노드를 삭제한 다음에 완전 이진 트리의 마지막 레벨의 가장 오른쪽에 위치한 노드를 우선 루트 노드의 자리로 옮긴다.

자식 노드와 우선 순위를 비교한 뒤에, 자식의 우선 순위가 더 높다면 위치를 서로 바꾼다.

자식 노드의 우선 순위가 더 낮을 때까지 비교와 교환을 반복한다.

힙의 시간복잡도

힙에서의 데이터 저장과 삭제의 과정을 보면, 최악의 경우에 트리의 높이의 해당하는 수만큼 비교 연산을 진행하게 되는 것을 알 수 있다. 즉 트리의 높이가 하나 늘어날 때마다 비교 연산의 횟수가 하나 증가한다.

그렇기 때문에 힙에서의 데이터 저장과 삭제의 시간복잡도는 $O(\log_2{n})$이다.

이는 데이터를 저장할 때 $O(n)$의 시간 복잡도를 가지는 배열과 연결 리스트 기반 우선순위 큐와 비교할 때 매우 효율적임을 알 수 있다.

그렇기 때문에 우선순위 큐를 구현할 때는 힙 자료구조를 사용한다.

힙의 구현

힙은 트리이다. 트리를 구현하는 방법에는 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다. 힙을 구현할 때는 배열을 사용하는 것이 효율적이다. 왜냐하면 연결 리스트를 사용하면 새로운 노드를 힙의 마지막 위치에 추가하는 것이 힘들기 때문이다.

배열 기반 힙

트리의 루트 노드부터 차례대로 1,2,3,... 번 인덱스를 지정하고 배열에 데이터를 저장한다.

이렇게 하면 왼쪽 자식 노드의 인덱스 값은 부모 노드의 인덱스 값 x 2를 하면 구할 수 있고, 오른쪽 자식 노드의 인덱스 값은 부모 노드의 인덱스 값 x 2 + 1, 부모 노드의 인덱스 값은 자식 노드의 인덱스 값 / 2를 하면 구할 수 있다.

힙을 구현하게 된다면 사실상 우선순위 큐를 구현한 것과 마찬가지이다.

우선순위 큐의 ADT

• void PQueueInit(PQueue* ppq, PriorityComp pc) : 우선순위 큐의 초기화를 진행한다. 우선순위 큐 생성 후 제일 먼저 호출되어야 하는 함수이다.
• int IsEmpty(PQueue* ppq) : 우선순위 큐가 빈 경우 TRUE(1)를, 그렇지 않으면 FALSE(0)를 반환한다.
• void Enqueue(PQueue* ppq, PQData data) : 매개변수 data로 전달된 값을 우선순위 큐에 저장한다.
• PQData Dequeue(PQueue* ppq) : 우선순위가 가장 높은 데이터를 삭제한다. 삭제된 데이터는 반환되며, 이 함수를 호출하기 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

우선순위 큐의 활용

• 다익스트라 알고리즘 : 최소 값을 찾을 때 우선순위 큐가 사용된다.
• A* 알고리즘 : 출발 지점부터 꼭짓점까지 가는 최단 거리를 찾아준다.
• 힙정렬 : 많은 힙정렬에서 우선순위 큐를 사용한다.
• 허프만 코딩 : 문자열을 트리를 이용해 2진수로 압축하는 알고리즘인 허프만 코딩에서 사용된다.