페어링 힙의 기본 정의
페어링 힙(pairing heap)은 빈 힙(empty heap)이거나, 하나의 루트 요소와 비어 있을 수 있는 페어링 트리들의 리스트로 구성된 페어링 트리(pairing tree)입니다.
여기에 적용되는 힙 순서 속성(heap ordering property)은 임의의 노드에 대해 그 부모 노드가 해당 노드 자신보다 크지 않아야 한다는 조건을 요구합니다. 즉, 부모 노드의 값은 항상 자식 노드의 값보다 작거나 같아야 합니다.
이 글의 설명은 decrease-key 연산을 지원하지 않는 순수 함수형(purely functional) 힙을 기준으로 진행됩니다.
타입 정의
페어링 힙은 다음과 같이 타입으로 표현할 수 있습니다.
type PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]])
type PairingHeap[Element] = Empty | PairingTree[Element]
첫 번째 정의에서 페어링 트리는 하나의 요소(element)와 서브힙(subheap)들의 리스트로 이루어지며, 두 번째 정의는 페어링 힙이 빈 상태(Empty)이거나 페어링 트리 중 하나임을 나타냅니다.
최소 페어링 힙과 최대 페어링 힙
페어링 힙은 두 가지 종류로 나뉩니다.
- 최소 페어링 힙(min pairing heap): 최소 우선순위 큐(min priority queue)를 표현할 때 사용됩니다.
- 최대 페어링 힙(max pairing heap): 최대 우선순위 큐(max priority queue)를 표현할 때 사용됩니다.
앞서 힙과 좌향 트리(leftist tree)를 다룬 내용과의 일관성을 위해, 여기서는 최대 페어링 힙을 명시적으로 설명합니다. 최소 페어링 힙도 동일한 원리로 유사하게 정의할 수 있습니다.
최대 페어링 힙의 구조
최대 페어링 힙은 단순히 최대 트리(max tree)로 정의됩니다. 즉, 각 노드의 값이 그 자식 노드들의 값보다 크거나 같은 트리를 의미합니다.
아래 그림은 네 개의 최대 페어링 힙 예시를 보여줍니다.
그림에서 주목해야 할 중요한 점은, 페어링 힙이 반드시 이진 트리일 필요는 없다는 사실입니다. 하나의 노드가 여러 개의 자식 노드를 가질 수 있으며, 이러한 유연한 구조 덕분에 페어링 힙은 구현이 간단하면서도 우수한 실제 성능을 보이는 우선순위 큐 자료구조로 널리 활용됩니다.