피보나치 힙 (Fibonacci Heap)

피보나치 힙 (Fibonacci Heap)

느슨한 구조의 힙으로, 감소 키(Decrease-Key)와 병합을 O(1) 상각 시간에 수행하여 다익스트라·프림 알고리즘의 이론적 최적 복잡도 달성

목적: 감소 키 최적화, 병합 효율, 그래프 알고리즘 가속화

특징: 느슨한 구조, 지연 통합, Cascading Cut, 상각 분석

구조

• •루트 리스트: 최소 힙 트리들의 이중 연결 리스트
• •min 포인터: 최소 루트 가리킴
• •자식 연결: 이중 원형 연결 리스트
• •marked 플래그: Cascading Cut 판단

연산 복잡도

• •insert: O(1) 상각 (루트 리스트에 추가)
• •find-min: O(1) (min 포인터)
• •merge: O(1) 상각 (루트 리스트 연결)
• •extract-min: O(log n) 상각 (통합 Consolidate)
• •decrease-key: O(1) 상각 (Cut + Cascading Cut)
• •delete: O(log n) 상각 (decrease-key + extract-min)

Cascading Cut: 자식 잃은 노드(marked)가 다시 자식 잃으면 부모에서 분리, 연쇄 분리

통합(Consolidate): extract-min 시 동일 차수 트리 병합, 이항 트리와 유사

장점: decrease-key O(1), 병합 O(1), 이론적 최적

단점: 상수 인자 큼, 구현 복잡, 실용적으로 이진 힙에 뒤처질 수 있음

다익스트라 적용: O((V + E) log V) → O(E + V log V) 로 개선

적용사례: 다익스트라, 프림 알고리즘, 이론적 분석

비교: 피보나치(decrease-key O(1)) vs 이진힙(O(log n)) vs 이항힙(병합O(log n))

연관: 힙, 다익스트라, 프림, 이항 힙, 상각 분석