About Double-Ended Priority Queue
Double-Ended Priority Queue(이중 우선순위 큐)
이중 우선순위 큐는 주어진 아이템 중 최대 아이템과 최소 아이템을 빠르게 찾기 위한 자료구조입니다.
Double-Ended Heap이라고도 불립니다. 키(아이템)들을 특정 순서로 저장하여, 최대, 최소 아이템을 효율적으로 삽입, 삭제합니다.
아이템을 오름차순과 내림차순 2가지 방법으로 제거할 수 있습니다.
DEPQ는 다음과 같은 인터페이스를 제공합니다.
- isEmpty()
- DEPQ가 비어있으면 참, 아니면 거짓을 반환합니다.
- size()
- DEPQ가 저장하고 있는 아이템의 개수를 반환합니다.
- getMin()
- 가장 우선순위가 낮은 아이템을 반환합니다.
- getMax()
- 가장 우선순위가 높은 아이템을 반환합니다.
- put(x)
- DEPQ에 아이템 x를 삽입합니다.
- removeMin()
- 가장 우선순위가 낮은 아이템을 삭제하고, 반환합니다.
- removeMax()
- 가장 우선순위가 높은 아이템을 삭제하고, 반환합니다.
만약 우선순위가 같은 아이템이 2개 이상이면, 먼저 삽입된 아이템이 선택됩니다. 삽입된 아이템의 우선순위는 언제든 바뀔 수 있습니다.
구현
이중 우선순위 큐는 다음과 같은 방법으로 구현할 수 있습니다.
- 균형 이진 탐색트리(최소 아이템과 최대 아이템이 각각 최좌측, 최우측 leaf에 있는)
- min-max heap, pairing heap과 같은 특수한 자료구조들
이중 구조 방식
이 방식에서는 최대와 최소 아이템을 위한 2가지 우선순위 큐가 유지됩니다. 두 우선순위 큐에 있는 공통된 아이템들은 1:1 대응이 유지됩니다.
최대와 최소 아이템들은 각각 최대힙과 최소힙의 root node에 유지됩니다.
- 최소 아이템 제거: 최소 힙에서 아이템을 제거하고, 최대 힙에서 해당 아이템을 제거합니다.
- 최대 아이템 제거: 최대 힙에서 아이템을 제거하고, 최소 힙에서 해당 아이템을 제거합니다.
Total Correspondence
절반의 아이템은 최소 힙에 저장하고, 나머지 절반은 최대 힙에 저장합니다. 최소 힙의 각 아이템은 최대 힙의 아이템에 1:1 대응됩니다. 만약 전체 아이템 개수가 홀수 이면, 하나의 아이템은 버퍼에 저장됩니다. 최소 힙에 있는 모든 아이템의 우선 순위는 최대 힙의 해당하는 아이템의 우선순위보다 작거나 같습니다.
Leaf Correspondence
Total Correspondence와는 다르게, 이 방식은 최대 힙과 최소 힙의 leaf 아이템들만 1:1 대응을 유지합니다. 만약 전체 아이템 개수가 홀수 이면, 하나의 아이템은 버퍼에 저장됩니다.
Interval Heaps
위의 대응 방식과 다르게, DEPQ는 interval heap을 이용햇 효율적으로 구현될 수 있습니다. Interval heap은 각 노드가 2개의 아이템(하한, 상한)을 가지는 embedded min-max heap과 같습니다.
Interval heap은 다음과 같은 특징을 지니는 완전 이진 트리입니다.
- 왼쪽 아이템은 오른쪽 아이템보다 작거나 같습니다.
- 두 아이템은 닫힌 범위 안에 정의됩니다.
- 루트를 제외한 모든 노드로 표현된 범위는 부모 노드의 하위 범위입니다.
- 왼쪽 아이템은 최소 힙을 정의합니다.
- 오른쪽 아이템은 최대 힙을 정의합니다.
아이템의 개수에 따라 2가지 경우가 존재합니다.
- 짝수개의 아이템
- 각 노드는 두가지 아이템 p,q(p ≤ q)를 가지며, 모든 노드는 닫힌 범위 [p,q]에 의해 표현됩니다.
- 홀수개의 아이템
- 마지막 노드를 제외한 모든 노드는 두가지 아이템 p,q(p ≤ q)를 가지며, 이 모든 노드는 닫힌 범위 [p,q]에 의해 표현된다. 마지막 노드는 [p,p]로 표현되는 하나의 아이템만을 가집니다.
아이템 삽입
아이템의 개수에 따라 2가지 경우가 존재합니다.
- 짝수개의 아이템
- 새로운 아이템을 삽입하면 새로운 노드가 생성됩니다. 만약 이 노드가 부모 범위의 왼쪽이면, 최소 힙에 속하는 것으로 간주되고, 오른쪽이라면 최대 힙에 속하는 것으로 간주됩니다. 범위 힙을 만족할 때까지 말단 노드부터 루트 노드까지 계속 비교합니다. 만약 아이템이 부모 노드의 범위 사이에 존재하면, 이 과정은 중단됩니다.
- 홀수개의 아이템
- 새로운 아이템을 삽입하면, 마지막 노드에 아이템이 처음에 삽입됩니다. 그리고 이전 노드의 아이템들과 계속 비교하면서 범위 힙을 만족시킵니다. 만약 새 아이템이 모든 범위를 만족하지 않으면, 새 아이템은 말단 노드부터 루트 노드까지 이동합니다.
아이템 삽입에 걸리는 시간은 O(logN)입니다.
아이템 제거
- 최소 아이템
- 범위 힙에서 최소 아이템은 루트 노드의 왼쪽에 있습니다. 이 아이템이 삭제되고, 반환됩니다. 마지막 노드에 있는 아이템은 루트 노드에 삽입되고, 범위 힙을 만족할 때까지 왼쪽 아이템들과 비교됩니다. 만약 왼쪽 아이템이 오른쪽 아이템보다 큰 경우에는, 두 아이템이 스왑됩니다. 그리고 다시 계속 비교합니다. 결국에는 다시 최소 아이템이 루트노드의 왼쪽 아이템이 됩니다.
- 최대 아이템
- 범위 힙에서 최대 아이템은 오른쪽 끝에 있습니다. 이 아이템이 삭제되고, 반환됩니다. 오른쪽 끝에 있는 아이템이 루트 노드에 삽입되고, 범위 힙을 만족할 때까지 오른쪽 아이템들과 비교됩니다. 결국에는 다시 최대 아이템이 루트노드의 오른쪽 아이템이 됩니다.
범위 힙을 이용하면, 최소와 최대 아이템이 효율적으로 삭제될 수 있습니다.
시간 복잡도
범위 힙
| Operation | Time Complexity |
|---|---|
| init() | O(n) |
| isEmpty() | O(1) |
| getMin() | O(1) |
| getMax() | O(1) |
| size() | O(1) |
| insert(x) | O(logn) |
| removeMin() | O(logn) |
| removeMax() | O(logn) |
페어링 힙
| Operation | Time Complexity |
|---|---|
| isEmpty() | O(1) |
| getMin() | O(1) |
| getMax() | O(1) |
| insert(x) | O(logn) |
| removeMax() | O(logn) |
| removeMin() | O(logn) |
응용
External Sorting
컴퓨터의 메모리가 부족할 때, 외부 정렬을 하기위해 사용될 수 있습니다. 이중 우선순위 큐를 이용하여 퀵 정렬을 할 수 있습니다.
