이항 힙 (Binomial Heap)

이항 힙 (Binomial Heap)

이항 트리(Binomial Tree)들의 집합으로 구성된 힙 자료구조로, 두 힙의 병합을 O(log n)에 수행할 수 있어 병합이 빈번한 우선순위 큐 연산에 적합

특징: 이항 트리 기반, 병합 효율적, 최소 힙 속성, 이진수 표현과 대응

이항 트리 (Binomial Tree) Bk

• •B₀: 단일 노드
• •Bk: 두 개의 Bk₋₁을 결합, 한쪽 루트를 다른 쪽 루트의 자식으로
• •Bk의 노드 수: 2^k, 높이: k, 루트 자식 수: k
• •깊이 d에서 노드 수: C(k, d) (이항 계수 → "이항" 트리 명칭 유래)

구조

• •차수(order)가 모두 다른 이항 트리들의 집합 (루트 리스트로 연결)
• •n개 노드 → 이진 표현의 1비트에 대응하는 이항 트리 보유 (예: n=13=1101₂ → B₃, B₂, B₀)
• •최대 ⌊log₂n⌋ + 1개의 이항 트리

연산 복잡도

• •insert: O(log n) 최악, O(1) 상각
• •find-min: O(log n) (루트 리스트 순회), O(1) (min 포인터 유지 시)
• •merge: O(log n) — 핵심 연산, 동일 차수 트리를 이진 덧셈처럼 병합(캐리 전파)
• •extract-min: O(log n) — 최소 루트 제거, 자식들을 새 힙으로 구성, 원래 힙과 병합
• •decrease-key: O(log n) — 키 감소 후 부모와 비교하며 상향 이동
• •delete: O(log n) — decrease-key(−∞) + extract-min

병합 과정: 두 힙의 루트 리스트를 차수 오름차순 병합 → 동일 차수 트리 결합(작은 루트가 부모) → 캐리 발생 시 연쇄 결합

비교

적용사례: 병합이 빈번한 우선순위 큐, 이산 이벤트 시뮬레이션, 그래프 알고리즘(프림, 다익스트라)

연관: 피보나치 힙, 이진 힙, 우선순위 큐, 프림 알고리즘, 상각 분석