피보나치 힙
Fibonacci Heap
목적
Fibonacci Heap (피보나치 힙)은 우선순위 큐(priority queue) 를 구현하는 고급 힙 자료구조 중 하나로,
기존의 이진 힙(Binary Heap)이나 이항 힙(Binomial Heap)에 비해 일부 연산에서 더 빠른 시간복잡도를 제공한다.
특히 insert, decrease_key, merge 등의 연산이 amortized (O(1)) 시간에 수행되도록 설계되어,
Dijkstra, Prim 알고리즘과 같은 그래프 기반 최적화 문제에서 매우 효율적으로 사용된다.
→ 게으른 연산(lazy operation) 구조를 바탕으로
필요할 때만 구조를 정리(consolidate)하여 전체 성능을 최적화하는 것이 핵심이다. 아래는 피보나치 힙을 구현하는 코드를 분석한 내용이다.
1단계: 임시 배열 A 생성
A = [None] * (math.log(self.n) * 2)- degree별 노드를 저장할 임시 배열 생성
- 최대 차수를 log₂(n)으로 추정하고 여유를 줘서 배열 생성
2단계: 현재 root list 복사
nodes = [w for w in self.iterate(self.root_list)]- root list를 순회하여 현재 루트 노드들을 모두 복사
3단계: 동일 차수 병합
for w in range(len(nodes)):
x = nodes[w]
d = x.degree
while A[d] is not None:
y = A[d]
if x.key > y.key:
x, y = y, x
self.heap_link(y, x)
A[d] = None
d += 1
A[d] = x- A[d]에 노드가 이미 있으면 → 병합
- 키가 더 작은 쪽을 부모로 하여 자식으로 연결
- 차수를 증가시키며 계속 병합
4단계: 병합된 노드들로 새 root list 구성
A 배열에 남은 노드들로 새로운 root list를 만든다.
self.root_list = None
self.min = None
for i in range(len(A)):
if A[i] is not None:
if self.root_list is None:
self.root_list = A[i]
A[i].left = A[i].right = A[i]
else:
# 기존 root list에 A[i] 삽입
A[i].left = self.root_list
A[i].right = self.root_list.right
self.root_list.right.left = A[i]
self.root_list.right = A[i]
# 최소 노드 갱신
if self.min is None or A[i].key < self.min.key:
self.min = A[i]A[i]가 비어있지 않다면, 해당 노드를 새 root list에 삽입- 처음 삽입하는 노드는 자기 자신을 left/right로 설정 (원형 이중연결 리스트)
- 이후 삽입되는 노드는 기존 리스트에 오른쪽으로 연결
- 동시에
min도 갱신하여 최종 최소 노드를 재지정
5단계: 최소 노드 재설정
for i in range(len(A)):
if A[i] is not None:
if A[i].key < self.min.key:
self.min = A[i]- 새 root list에서 가장 작은 key를 가진 노드를
self.min으로 설정
6단계: 완료
- root list가 다시 정리되어
degree 중복 없이 정렬된 트리 forest로 유지됨 - 이후의
extract_min,decrease_key등 연산의 성능 최적화
더 자세한 이야기는
develop을 꿈꾸는