C++ 이항 힙(Binomial Heap)이란?
이항 힙(Binomial Heap)은 이진 힙(Binary Heap)을 확장한 자료구조로, 기존 이진 힙이 제공하는 모든 연산에 더해 훨씬 빠른 병합(merge) 및 합집합(union) 연산을 지원하는 것이 특징입니다.
이항 힙은 여러 개의 이항 트리(Binomial Tree)들의 집합으로 구성됩니다.
이항 트리(Binomial Tree)란?
차수(order)가 k인 이항 트리는 차수가 k-1인 두 개의 이항 트리를 가져와, 하나를 다른 트리의 가장 왼쪽 자식으로 붙여 만들 수 있습니다.
차수가 k인 이항 트리는 다음과 같은 성질을 가집니다.
노드의 개수는 정확히 2k개입니다.
트리의 깊이(depth)는 k입니다.
깊이 i(i = 0, 1, ..., k)에는 정확히 kCi(이항 계수)개의 노드가 존재합니다.
루트의 차수(degree)는 k이며, 루트의 자식들은 왼쪽에서 오른쪽 순서로 각각 차수가 k-1, k-2, ..., 0인 이항 트리로 취급됩니다.
이항 힙의 정의와 예시
이항 힙은 각 이항 트리가 최소 힙(Min Heap) 속성을 만족하는 이항 트리들의 집합으로 정의됩니다. 또한 어떤 차수에 대해서도 해당 차수를 가진 이항 트리는 최대 한 개만 존재할 수 있습니다.
예를 들어, 노드가 12개인 이항 힙은 두 개의 이항 트리들의 집합으로 표현되며, 왼쪽에서 오른쪽으로 차수가 2와 3인 이항 트리들로 구성됩니다.
이항 힙과 수의 이진 표현의 관계
흥미롭게도 노드가 m개인 이항 힙에서 이항 트리의 개수는 m의 이진 표현에서 1(set bit)의 개수와 같습니다.
예를 들어 m이 13이라면, 13의 이진 표현(00001101)에는 1이 3개 있으므로 이항 트리도 3개가 됩니다. 나아가 각 이항 트리의 차수는 set bit의 위치와 대응시킬 수 있습니다. 이러한 관계를 통해 노드가 'm'개인 이항 힙 안에는 O(log m)개의 이항 트리가 존재한다는 결론을 도출할 수 있습니다.
이항 힙의 주요 연산
이항 힙에서 union()이 핵심 연산이며, 나머지 대부분의 연산은 내부적으로 이 union() 연산을 활용해 구현됩니다. union() 연산은 두 개의 이항 힙을 하나로 합치는 역할을 담당합니다.
insert(h, K) − 키 'K'를 이항 힙 'h'에 삽입합니다. 먼저 키 'K' 하나만 가진 새로운 이항 힙을 생성한 뒤, 기존 힙 h와 새 힙에 대해 union()을 호출합니다.
getMin(h) − 가장 단순한 방법은 이항 트리들의 루트 목록을 순회하며 가장 작은 키를 반환하는 것입니다. 이 방식은 O(log m)의 시간이 필요하지만, 최솟값을 가진 루트를 가리키는 포인터를 유지하면 O(1)까지 개선할 수 있습니다.
extractMin(h) − 이 연산 역시 union()을 활용합니다. 먼저 getMin()을 호출해 최솟값을 가진 이항 트리를 찾고, 해당 노드를 제거한 후 제거된 노드의 모든 서브트리들을 결합해 새로운 이항 힙을 만듭니다. 마지막으로 기존 힙 h와 새로 만든 힙에 대해 union()을 호출합니다. 이 연산은 O(log m)의 시간이 소요됩니다.
delete(h) − 이진 힙과 마찬가지로, 삭제 연산은 먼저 해당 키를 음의 무한대(-∞)로 줄인 다음 extractMin()을 호출하는 방식으로 수행됩니다.
decreaseKey(h) − 감소시킨 키를 부모 노드의 키와 비교하고, 부모의 키가 더 크다면 두 키를 교환한 뒤 부모에 대해 재귀적으로 반복합니다. 부모의 키가 더 작은 노드에 도달하거나 루트 노드에 도달하면 종료됩니다. decreaseKey()의 시간 복잡도는 O(log m)입니다.