랜덤화 병합 힙(Randomized Meldable Heap, 병합 가능 우선순위 큐라고도 불림)은 삽입(insertion), 삭제(deletion), 그리고 최솟값 검색 연산인 findMin 등 다양한 기본 연산을 지원합니다. 특히 삽입과 삭제 연산은 병합 힙 고유의 추가 연산인 Meld(A1, A2)를 기반으로 구현됩니다.
Meld(병합)
Meld(merge라고도 불리는) 연산의 기본 목표는 두 개의 힙(각 힙의 루트 노드를 기준으로) A1과 A2를 하나로 병합하여 단일 힙 노드를 반환하는 것입니다. 반환된 노드는 A1과 A2에 뿌리를 둔 두 서브트리의 모든 원소를 포함하는 힙의 루트 노드가 됩니다.
이 Meld 연산의 가장 훌륭한 특징은 재귀적으로 정의할 수 있다는 점입니다. 두 힙 중 하나가 null이면 빈 집합과의 병합이 되므로, 메서드는 비어 있지 않은 힙의 루트 노드를 그대로 반환합니다. A1과 A2가 모두 nil이 아니라면 A1 > A2인지 확인하고, 참이라면 두 노드를 교환(swap)합니다. 이를 통해 A1 < A2가 보장되므로 병합된 힙의 루트 노드는 항상 A1을 값으로 갖게 됩니다. 이후 A1.left 또는 A1.right와 A2를 재귀적으로 병합하는데, 어느 쪽으로 병합할지는 동전 던지기(coin toss)로 결정됩니다. 바로 이 지점에서 무작위성(randomization)이 적용되는 것입니다.
function Meld(Node A1, Node A2)
if A1 is nil => return A2
if A2 is nil => return A1
if A1 > A2 => swap A1 and A2
if coin_toss is 0 => A1.left = Meld(A1.left, A2)
else A1.right = Meld(A1.right, A2)
return A1
Insert(삽입)
Meld 연산이 준비되고 나면 병합 힙에 새 원소를 삽입하는 일은 매우 간단합니다. 먼저 값 p를 담는 새 노드 a를 생성한 뒤, 이 노드를 힙의 루트 노드와 병합하기만 하면 됩니다.
function Insert(p)
Node a = new Node
a.p = p
root = Meld(a, root)
root.parent = nil
increment node count
Remove(삭제)
삽입 연산만큼 쉬운 Remove() 역시 Meld 연산을 활용해 힙의 루트 노드를 제거합니다. 루트 노드의 두 자식 노드를 병합하고, 반환된 노드를 새 루트로 지정하는 방식으로 수행됩니다.
function Remove()
rootNode = Meld(rootNode.left, rootNode.right)
if rootNode is not nil => rootNode.parent = nil
decrement node count
FindMin(최솟값 검색)
랜덤화 병합 힙에서 가장 간단한 연산일 수 있는 FindMin()은 힙의 루트 노드에 저장된 현재 원소, 즉 최솟값을 그대로 반환합니다.
추가 연산
병합 힙에 적용할 수 있으며, 최악의 경우에도 O(log n)의 효율을 보장하는 추가 연산들은 다음과 같습니다.
- Remove(a) - 노드 a와 해당 키를 힙에서 제거합니다.
- Absorb(P) - 병합 힙 P의 모든 원소를 현재 힙으로 흡수하며, 이 과정에서 P는 비워집니다.
- DecreaseKey(a, q) - 노드 a의 키 값을 q로 감소시킵니다(사전 조건: q <= a.p).