우선순위 큐 (Priority Queue) 개념 및 구현
일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다.
하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다.
우선순위 큐는 다음과 같은 속성을 가지고 있습니다.
- 모든 항목에는 우선순위가 있습니다.
- 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다.
- 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됩니다.
4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같습니다.
(여기서 높은 값이 높은 우선순위를 갖는다고 가정하겠습니다.)
input : 4 → 8 → 2
큐 : 4 → 8 → 2
우선순위 큐 : 8 → 4 → 2
기본 동작
우선순위 큐는 다음 기능을 지원합니다.
- enqueue()- queue에 새 요소를 삽입합니다.
- dequeue() - queue에서 최대 우선 순위 요소를 삭제하고 그 값을 반환합니다.
- peek() - queue에서 최대 우선순위 요소를 반환합니다.
구현
일반적인 우선순위 큐 구현 방식에는 배열, 연결 리스트, 힙이 있습니다.
각 구현 방식에 시간복잡도는 다음과 같습니다.
| 구현 방법 | enqueue() | dequeue() |
| 배열 (unsorted array) | O(1) | O(N) |
| 연결 리스트 (unsorted linked list) | O(1) | O(N) |
| 정렬된 배열 (sorted array) | O(N) | O(1) |
| 정렬된 연결 리스트 (sorted linked list) | O(N) | O(1) |
| 힙 (heap) | O(logN) | O(logN) |
*N : 노드 수
힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙을 가지고 구현을 합니다.
힙에 대한 내용은 아래 링크를 참고하시기 바랍니다.
[자료구조] 힙 (Heap) or 이진 힙(binary heap)
우선순위 큐 요소의 구조는 다음과 같이 나타낼 수 있습니다.
struct node {
int data;
int priority;
}
구현의 편의를 위해 다음을 가정하여 구현하겠습니다.
- 배열에는 우선순위만 들어있습니다.
- 값이 클 수록 우선순위가 높습니다. (최대 힙)
- size변수는 전역변수이며 힙에 있는 요소수를 나타냅니다.
- 루트 노드는 인덱스 1에 위치합니다.
peek()
peek()은 우선순위 큐에서 최대 우선순위 값을 반환합니다.
최대 우선순위 값(최대 힙)은 항상 루트에 있으므로 루트 값을 반환합니다.
구현
int peek(int arr[]) {
return arr[1];
}시간 복잡도: O(1)
enqueue()
enqueue()는 우선순위 큐(최대 힙)에 요소를 삽입하는 작업을 합니다.
삽입 작업은 다음과 같습니다.
- 힙 끝에 새 요소를 삽입합니다.
- 부모 노드와 비교하여 힙 속성을 위배하는 경우 부모 노드와 값을 바꿉니다.
- 힙 속성이 유지될 때까지 2번 작업을 반복합니다.
다음 그림은 enqueue()를 수행하는 예입니다.
구현
void enqueue(int arr[], int val)
{
int i = 0;
if (size == MAX_LEN) { // 배열에 공간이 없으면 실패
printf("Overflow: Could not insertKey\n");
}
// 힙 끝에 요소 삽입.
size ++;
i = size;
arr[i]= val;
// 우선순위가 부모 노드가 더 작다면 교환하고 부모 노드부터 다시 비교, 힙속성을 유지할 때까지 반복함.
while(i > 1 && arr[i/2] < arr[i]) {
swap(arr[i/2], arr[i]);
i = i/2;
}
}시간 복잡도: O(logN)
heapify()
heapify는 힙 속성을 유지하는 작업을 합니다. 위에서 아래로 내려가면서 작업을 합니다.
max heap에서 heapify의 작업은 다음과 같습니다.
- 자식 노드와 우선순위를 비교합니다.
- 만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 가장 우선순위가 높은 노드와 교환합니다.
- 힙 속성이 유지 될 때까지 1,2번 과정을 반복합니다.
다음 그림은 루트 노드에서 max_heapify()를 수행하는 예입니다.
구현
void max_heapify (int arr[], int i)
{
int largest = i;
int left = 2*i //left child
int right = 2*i +1 //right child
// 현재 요소 i와 자식 노드의 값을 비교
if(left <= size && arr[left] > arr[i] )
largest = left;
if(right <= size && arr[right] > arr[largest] )
largest = right;
// 자식 노드의 값이 더 크다면 교환하고 교환된 자식 노드부터 heapify 진행
if(largest != i ) {
swap (arr[i] , arr[largest]);
max_heapify (h, largest);
}
}시간 복잡도: O(logN)
dequeue()
dequeue()는 우선 순위 큐(최대 힙)에 최대 우선순위 요소를 삭제하고 그 값을 반환하는 작업을 합니다.
삭제 작업은 다음과 같습니다.
- 루트 노드의 값을 추출합니다.
- heap 마지막 요소를 루트 노드에 배치합니다.
- 마지막 요소는 제거합니다.
- 루트 노드부터 heapify를 수행합니다.
다음 그림은 dequeue()를 수행하는 예입니다.
구현
int dequeue (int arr[]) {
if(size == 0) {
printf("empty\n");
}
// 루트 노드 값을 리턴값에 저장한 뒤, 마지막 요소를 루트노드에 배치함
Node max = arr[1];
arr[1] = arr[size];
size --;
// 루트 노드부터 heapify 수행
max_heapify(arr, 1);
return max;
}시간 복잡도: O(logN)
사용 사례
- CPU 스케줄링
- Dijkstra's shortest path algorithm, Prim's Mininum Spanning tree
- 우선순위를 포함한 모든 queue 응용
