이항 힙(Binomial heap)은 컴퓨터 과학에서 사용되는 자료 구조로서, 우선순위 큐(priority queue)를 효율적으로 구현하기 위한 힙 기반의 자료 구조이다. 이항 힙은 이항 트리(binomial tree)들의 집합으로 구성되며, 힙 성질(heap property)과 이항 트리의 구조적 특성을 결합하여 삽입, 병합, 최소값 추출 등의 연산을 효율적으로 수행할 수 있도록 설계되어 있다.
개요
이항 힙은 여러 개의 이항 트리로 구성되며, 각 트리는 힙 성질을 만족한다. 즉, 각 노드의 키 값은 그 자식 노드의 키 값보다 작거나 같아야 한다 (최소 힙 기준). 이항 힙 내의 이항 트리는 서로 다른 차수(order)를 가지며, 동일한 차수의 트리가 두 개 이상 존재하지 않는다. 이와 같은 구조는 이항 계수(binomial coefficient)의 이진 표현과 유사한 방식으로 구성되며, 덕분에 이항 힙의 병합(Merge) 연산이 특히 효율적이다.이항 힙은 주로 병합 연산이 자주 발생하는 환경에서 사용되며, 힙 간의 병합을 O(log n)의 시간 복잡도로 수행할 수 있다는 점에서 기존의 이진 힙(binary heap)보다 유리하다. 주요 연산의 시간 복잡도는 다음과 같다:
- 삽입(insert): O(log n)
- 최소값 추출(extract-min): O(log n)
- 병합(merge): O(log n)
- 감소키(decrease-key): O(log n)
- 삭제(delete): O(log n)
어원/유래
"이항 힙(binomial heap)"이라는 용어는 "이항 계수(binomial coefficient)" 또는 "이항 분포(binomial distribution)"와 관련된 수학적 구조에서 유래하였다. 이항 힙의 구조는 n개의 노드를 가진 이항 힙이 이항 계수의 이진 표현과 유사하게 구성된다는 점에서 이름이 붙여졌다. 예를 들어, 노드 수가 13인 이항 힙은 차수 0, 2, 3인 이항 트리로 구성되며, 이는 13의 이진 표현인 1101과 대응된다. 이러한 구조적 유사성 때문에 "binomial"이라는 용어가 사용되었다.이항 힙은 Jean Vuillemin이 1978년에 처음 제안하였으며, 이후 우선순위 큐 구현의 효율성을 높이기 위한 다양한 파생 구조(예: 피보나치 힙)의 기초가 되었다.
특징
이항 힙의 주요 특징은 다음과 같다:- 여러 개의 이항 트리로 구성되며, 각 트리는 정형화된 계층 구조를 가진다.
- 이항 트리의 차수 k인 트리는 정확히 2^k 개의 노드를 가지며, 루트의 차수는 k이다.
- 이항 힙 내에서는 각 차수의 이항 트리가 최대 하나만 존재한다.
- 병합 연산이 매우 효율적이며, 이진 힙보다 병합이 빈번한 상황에서 유리하다.
- 이항 트리 간의 병합은 동일한 차수의 두 트리를 하나의 더 큰 차수의 트리로 결합하는 방식으로 이루어진다.
관련 항목
- 우선순위 큐 (Priority Queue)
- 이진 힙 (Binary Heap)
- 피보나치 힙 (Fibonacci Heap)
- 이항 트리 (Binomial Tree)
- 자료 구조 (Data Structure)
- 힙 성질 (Heap Property)