혼합 가능한 우선순위 큐(Meldable Priority Queue)
정의
랜덤화 혼합 힙(Randomized Meldable Heap, 또는 Randomized Meldable Priority Queue)은 내부 구조가 힙 순서(heap-order)를 따르는 이진 트리로 구성된 우선순위 큐 기반 자료구조입니다. 다만 일반적인 힙과 달리, 기반이 되는 이진 트리의 모양(shape)에 대한 엄격한 제약 조건은 존재하지 않는다는 점이 특징입니다.
주요 장점
랜덤화 혼합 힙은 유사한 다른 자료구조에 비해 여러 가지 실질적인 이점을 제공합니다.
- 다른 우선순위 큐 자료구조보다 더 단순한 접근 방식을 제공하여 구현과 이해가 쉽습니다.
- 모든 연산이 적용하기 간편하며, 시간 복잡도 상수(constant factor)가 작아 실제 성능이 좋습니다.
- 트리의 균형(balance) 조건을 유지할 필요가 없고, 노드 내부에 위성 정보(satellite information)를 저장하지 않아도 됩니다.
- 최악의 경우에도 우수한 시간 효율성을 보입니다. 대부분의 경우 각 연산의 실행 시간은 높은 확률로 로그 시간(logarithmic time) 안에 완료됩니다.
스큐 힙(Skew Heap)
스큐 힙(skew heap, 또는 자기 조절 힙(self-adjusting heap))은 이진 트리 형태로 구현되는 힙 자료구조입니다.
스큐 힙의 가장 큰 장점은 일반적인 이진 힙(binary heap)보다 병합(merge) 연산을 훨씬 빠르게 수행할 수 있다는 점입니다.
이진 힙과 달리 구조적 제약(structural constraints)이 없기 때문에, 트리의 높이가 반드시 로그 스케일을 유지한다는 보장은 없습니다. 대신 다음 두 가지 조건만 만족하면 됩니다.
- 일반적인 힙 순서(heap order)만 유지하면 됩니다. 즉, 루트가 최솟값이어야 하며, 이 규칙이 모든 서브트리에 재귀적으로 적용됩니다. 단, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 한다는 균형 속성(balanced property)은 요구되지 않습니다.
- 스큐 힙의 핵심 연산은 오직 병합(Merge) 하나뿐입니다. 삽입(insert), 최솟값 추출(extractMin()) 등 나머지 연산들은 모두 병합 연산만으로 구현할 수 있습니다.
예제
첫 번째 스큐 힙이 다음과 같다고 가정해 보겠습니다.
두 번째 힙은 아래와 같습니다.
두 힙을 병합하면 최종적으로 다음과 같은 형태의 트리를 얻게 됩니다.
재귀적 병합 과정(Recursive Merge Process)
merge(a1, a2) a1과 a2를 병합할 두 개의 최소 스큐 힙(min skew heap)이라 하자. a1의 루트가 a2의 루트보다 작다고 가정한다. (그렇지 않다면 두 힙을 서로 교환(swap)하면 동일한 상황을 만들 수 있다.) 1. a1->left와 a1->right를 서로 교환한다. 2. a1->left = merge(a2, a1->left)