페어링 힙(Pairing Heap)이란?
페어링 힙(pairing heap)은 구현이 비교적 간단하면서도 실질적인 분할 상환(amortized) 성능이 매우 뛰어난 힙(heap) 데이터 구조의 한 종류입니다.
페어링 힙은 힙 순서(heap order)를 유지하는 다방향(multiway) 트리 구조로, 단순화된 피보나치 힙(Fibonacci heap)으로 표현할 수 있습니다.
프림(Prim)의 최소 신장 트리(MST) 알고리즘과 같은 알고리즘을 구현할 때 "견고한 선택(robust choice)"으로 평가받으며, 최소 힙(min-heap)을 기준으로 다음과 같은 연산들을 지원합니다.
페어링 힙의 주요 연산
- find-min(최솟값 찾기) – 힙의 최상단(root) 요소를 반환하는 함수입니다.
- meld(병합) – 두 루트 요소를 비교하여 더 작은 값을 결과 힙의 루트로 두고, 더 큰 값과 그 서브트리는 해당 루트의 자식으로 추가하는 함수입니다.
- insert(삽입) – 삽입할 요소로 새로운 힙을 생성한 뒤, 원래 힙과 meld하는 함수입니다.
- decrease-key(키 감소, 선택 사항) – 감소시킬 키를 루트로 하는 서브트리를 제거하고, 해당 키를 더 작은 값으로 교체한 후 결과를 다시 힙에 meld하는 함수입니다.
- delete-min(최솟값 삭제) – 루트를 제거한 후, 서브트리들을 반복적으로 meld하여 하나의 트리만 남을 때까지 병합하는 함수입니다. 이 과정에서 다양한 병합 전략이 활용됩니다.
노드 구조
각 노드는 왼쪽 자식(leftmost child)을 가리키는 포인터를 가지며, 왼쪽 자식 포인터는 자신의 다음 형제(next sibling) 노드를 가리킵니다. 아래는 페어링 힙의 예시입니다.
시간 복잡도
페어링 힙의 시간 복잡도 분석은 스플레이 트리(splay tree)의 분석 방법에서 큰 영감을 받았습니다. delete-min 연산의 분할 상환 시간은 O(log n)으로 간주되며, find-min, meld, insert 연산은 O(1)의 분할 상환 시간에 실행됩니다.