Priority Queues
상위 문서: Data Structures
개요
해당 문서에서는 알고리즘등에서 많이 응용되는 우선순위 큐(priority queue)에 대해 설명한다. 우선순위 큐는 FIFO 원칙을 따르는 일반적인 queue와는 달리, 우선순위 큐는 각 원소에 우선순위를 부여하고, 우선순위가 가장 높은 우선순위 원소가 먼저 처리되는 자료구조이다. 즉 단순 정렬과 다르게, 새로운 작업이 들어올 때마다 전체를 다시 정렬하지 않고 효율적으로 관리할 수 있는 구조를 제공한다.
데이터를 한 번 정렬해 놓으면, “가장 작은 값”이나 “가장 큰 값”을 바로 알 수 있다. 하지만 이러한 방식으로 가장 중요한 원소를 찾는 것은 새로운 데이터가 들어올 때마다 번거롭게 전체를 다시 정렬해야 한다는 문제가 있다.(O(n log(n)) 시간) 하지만 우선순위 큐는 가장 중요한(작은/큰) 원소만 빠르게 찾을 수 잇게 설계된 자료구조이므로, 정렬을 유지할 필요가 없다. 새로운 데이터가 들어오면 그냥 힙에 삽입하면 되고, 이는 O(log n)만 걸린다.
Priority Queue Operations
아래는 우선순위 큐에서 지원하는 기본적인 연산 3가지이다:
- Insert(Q, x): 새로운 원소 x를 우선순위 큐 Q에 삽입한다.
- 원소는 보통 (key, value) 형태로 들어오며, key가 우선순위를 나타낸다.
- 시간 복잡도는 O(log n)이다. (힙에서 삽입 시 트리 높이만큼 조정 필요)
- Find-Minimum(Q) / Find-Maximum(Q): 큐 안에서 가장 작은 key(또는 가장 큰 key)를 가진 원소를 반환한다.
- 최소 힙(min-heap)이라면 Find-Minimum은 O(1)로 가능.
- 최대 힙(max-heap)이라면 Find-Maximum은 O(1)로 가능.
- 시간 복잡도는 O(log n)이다. (루트 제거 후 재정렬 필요)
- Delete-Minimum(Q) / Delete-Maximum(Q): 가장 작은 key(혹은 큰 key)를 가진 원소를 큐에서 제거한다.
- 시간 복잡도는 O(1)이다. (힙의 루트 확인만 하면 됨)
Heap
힙(Heap)은 완전 이진트리(complete binary tree) 기반의 자료구조이다. 즉, 모든 레벨이 다 채워져 있고, 마지막 레벨만 예외적으로 왼쪽부터 채워지는 트리를 기반으로 한다. 힙 자료 구조는 아래와 같은 조건을 만족해야 한다.
- 리프(leaf)노드는 마지막 두 층에서만 리프가 분포할 수 있다.
- 마지막 레벨은 노드 들이 왼쪽부터 순서대로 채워지고, 그 위 레벨들은 전부 채워져야 한다.
- 루트의 키는 자식들의 키보다 작거나 같아야 하며(min heap의 경우), 모든 서브트리도 다시 힙 구조여야 한다.
조건 1, 2는 트리의 형태(shape) 를, 조건 3은 순서 규칙(ordering) 을 규정한다.
Applications of Priority Queues
사실은 일반적인 stack(LIFO)이나 queue(FIFO)도 사실은 특수한 형태의 우선순위 큐이다. stack은 가장 최근에 들어온 원소가 우선순위가 높고, queue는 가장 먼저 들어온 원소가 우선순위가 높은 것이다.
우선순위 큐는 시뮬레이션(simulation) 에서 매우 자주 활용된다. 시뮬레이션은 시간의 흐름에 따라 사건(event)이 발생하는데, 각 사건의 발생 시간이 다르다. 이때 우선순위 큐를 이용하면 “가장 빨리 일어날 사건(최소 시간)”을 효율적으로 뽑아낼 수 있다. 예를 들면 공항에서 다음 비행기 착륙, 주차장에서 다음 차량 입출차 등이 있다.
