이항 힙(Binomial Heap)은 여러 개의 이항 트리(Binomial Tree)로 구성된 자료구조입니다. 이항 힙은 우선순위 큐를 효율적으로 구현할 수 있어 알고리즘 설계에서 널리 활용됩니다. 이번 글에서는 이항 트리의 재귀적 정의부터 이항 힙의 성질과 예시까지 차근차근 살펴보겠습니다.
이항 트리(Binomial Tree)란?
이항 트리 Bk는 재귀적으로 정의되는 순서 트리(ordered tree)입니다.
B0는 단 하나의 노드로 이루어진 가장 기본적인 형태입니다.
Bk(k ≥ 1)는 두 개의 이항 트리 Bk-1을 서로 연결(link)하여 만듭니다. 이때 한 트리의 루트가 다른 트리 루트의 가장 왼쪽 자식이 됩니다.
아래 그림은 몇 가지 이항 힙의 예시입니다.
이항 트리의 주요 성질
이항 트리 Bk는 다음과 같은 중요한 수학적 성질을 가집니다.
이항 트리 Bk는 총 2k개의 노드를 가집니다.
트리의 높이(height)는 k입니다.
깊이 i(0 ≤ i ≤ k)에 있는 노드의 개수는 정확히 이항계수 $$\left(\begin{array}{c}k\\ j\end{array}\right)$$개입니다. '이항'이라는 이름도 바로 이 이항계수에서 유래했습니다.
이항 힙(Binomial Heap)의 정의
이항 힙 H는 이항 트리들의 집합(set)으로 정의되며, 다음 두 가지 성질을 만족해야 합니다.
H에 속한 각 이항 트리는 힙 순서(heap-ordered)를 유지합니다. 즉, 모든 노드의 키 값은 자신의 부모 노드의 키 값보다 크거나 같습니다(min-heap 관점).
H 안에는 동일한 차수(degree)를 가진 루트를 가진 이항 트리가 최대 하나만 존재합니다.
이항 힙 예시
위 그림의 이항 힙 H는 이항 트리 B0, B2, B3로 구성되어 있습니다. 각 트리는 각각 1개, 4개, 8개의 노드를 가지며, 전체 노드 수는 n = 13개입니다.
흥미로운 점은 노드 수 n을 이진수로 표현하면 13 = 1101(2)이 되고, 이는 B3, B2, B0의 존재와 정확히 일치한다는 것입니다. 또한 각 이항 트리의 루트들은 차수가 증가하는 순서로 연결 리스트(linked list) 형태로 연결되어 있어, 힙 연산 시 효율적인 탐색과 병합이 가능합니다.