Priority Queues

상위 문서: Data Structures

개요

해당 문서에서는 알고리즘등에서 많이 응용되는 우선순위 큐(priority queue)에 대해 설명한다. 우선순위 큐는 FIFO 원칙을 따르는 일반적인 queue와는 달리, 우선순위 큐는 각 원소에 우선순위를 부여하고, 우선순위가 가장 높은 우선순위 원소가 먼저 처리되는 자료구조이다. 즉 단순 정렬과 다르게, 새로운 작업이 들어올 때마다 전체를 다시 정렬하지 않고 효율적으로 관리할 수 있는 구조를 제공한다.

데이터를 한 번 정렬해 놓으면, “가장 작은 값”이나 “가장 큰 값”을 바로 알 수 있다. 하지만 이러한 방식으로 가장 중요한 원소를 찾는 것은 새로운 데이터가 들어올 때마다 번거롭게 전체를 다시 정렬해야 한다는 문제가 있다.(O(n log(n)) 시간) 하지만 우선순위 큐는 가장 중요한(작은/큰) 원소만 빠르게 찾을 수 잇게 설계된 자료구조이므로, 정렬을 유지할 필요가 없다. 새로운 데이터가 들어오면 그냥 힙에 삽입하면 되고, 이는 O(log n)만 걸린다.

Priority Queue Operations

아래는 우선순위 큐에서 지원하는 기본적인 연산 3가지이다:

1. Insert(Q, x): 새로운 원소 x를 우선순위 큐 Q에 삽입한다.
   • 원소는 보통 (key, value) 형태로 들어오며, key가 우선순위를 나타낸다.
   • 시간 복잡도는 O(log n)이다. (힙에서 삽입 시 트리 높이만큼 조정 필요)
2. Find-Minimum(Q) / Find-Maximum(Q): 큐 안에서 가장 작은 key(또는 가장 큰 key)를 가진 원소를 반환한다.
   • 최소 힙(min-heap)이라면 Find-Minimum은 O(1)로 가능.
   • 최대 힙(max-heap)이라면 Find-Maximum은 O(1)로 가능.
   • 시간 복잡도는 O(log n)이다. (루트 제거 후 재정렬 필요)
3. Delete-Minimum(Q) / Delete-Maximum(Q): 가장 작은 key(혹은 큰 key)를 가진 원소를 큐에서 제거한다.
   • 시간 복잡도는 O(1)이다. (힙의 루트 확인만 하면 됨)

Heap

힙(Heap)은 완전 이진트리(complete binary tree) 기반의 자료구조이다. 즉, 모든 레벨이 다 채워져 있고, 마지막 레벨만 예외적으로 왼쪽부터 채워지는 트리를 기반으로 한다. 힙 자료 구조는 아래와 같은 조건을 만족해야 한다.

1. 리프(leaf)노드는 마지막 두 층에서만 리프가 분포할 수 있다.
2. 마지막 레벨은 노드 들이 왼쪽부터 순서대로 채워지고, 그 위 레벨들은 전부 채워져야 한다.
3. 루트의 키는 자식들의 키보다 작거나 같아야 하며(min heap의 경우), 모든 서브트리도 다시 힙 구조여야 한다.

조건 1, 2는 트리의 형태(shape) 를, 조건 3은 순서 규칙(ordering) 을 규정한다. Figure 1은 각각 트리 구조와 배열 인덱스를 통해 표현한 힙 자료구조의 예시이다. 힙은 이러한 조건을 통해서 partial order를 유지한다. 이는 전체를 정렬하지 않아도 최솟값/최댓값을 빠르게 식별 가능하게 한다.

Array-Based Heaps

일반적으로 트리는 각 노드가 자식 포인터를 가지지만, 힙은 배열 기반 표현이 더 자연스럽다. 배열 인덱스를 통해 binary tree를 나타내기 위해서는 아래와 같은 규칙을 가지면 된다:

1. 노드 k의 왼쪽 자식: 2k
2. 오른쪽 자식: 2k+1
3. 부모: ⌊k/2⌋

이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 $n<2^h$일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.

Applications of Priority Queues

사실은 일반적인 stack(LIFO)이나 queue(FIFO)도 사실은 특수한 형태의 우선순위 큐이다. stack은 가장 최근에 들어온 원소가 우선순위가 높고, queue는 가장 먼저 들어온 원소가 우선순위가 높은 것이다.

우선순위 큐는 시뮬레이션(simulation) 에서 매우 자주 활용된다. 시뮬레이션은 시간의 흐름에 따라 사건(event)이 발생하는데, 각 사건의 발생 시간이 다르다. 이때 우선순위 큐를 이용하면 “가장 빨리 일어날 사건(최소 시간)”을 효율적으로 뽑아낼 수 있다. 예를 들면 공항에서 다음 비행기 착륙, 주차장에서 다음 차량 입출차 등이 있다.