피보나치 힙(Fibonacci Heap)은 여러 개의 트리(tree)를 모아놓은 자료구조로, 기본적으로 이항 힙(Binomial Heap)을 바탕으로 느슨하게 설계된 구조입니다. 두 자료구조는 비슷해 보이지만 중요한 차이점이 있습니다. 이항 힙을 구성하는 트리들이 '순서가 있는(orderd)' 트리라면, 피보나치 힙을 구성하는 트리들은 루트(root)를 가지고는 있지만 자식 간 순서가 정해져 있지 않은(unordered) 트리라는 점입니다.
피보나치 힙의 노드 구조
피보나치 힙에서 각 노드 x는 다음과 같은 포인터(pointer)들을 가지고 있습니다.
- p[x] : 부모 노드(parent)를 가리키는 포인터
- child[x] : 자식 노드 중 하나를 가리키는 포인터
노드 x의 모든 자식들은 원형 이중 연결 리스트(circular doubly linked list) 형태로 서로 연결되어 있으며, 이를 x의 차일드 리스트(child list)라고 부릅니다.
차일드 리스트에 있는 각 자식 노드 y는 left[y]와 right[y]라는 포인터를 통해 왼쪽 형제(sibling)와 오른쪽 형제를 각각 가리킵니다. 만약 노드 y가 유일한 자식이라면 left[y] = right[y] = y가 되어 자기 자신을 가리키게 됩니다. 또한 차일드 리스트 내에서 형제 노드들이 나타나는 순서는 임의적(arbitrary)으로 정해집니다.
피보나치 힙 예시
아래 그림은 피보나치 힙 H의 예시입니다.
이 피보나치 힙 H는 루트 리스트(root list)에 연결된 5개의 트리와 총 16개의 노드로 구성되어 있습니다. 화살표가 있는 선은 루트 리스트를 나타내며, 리스트에서 최솟값을 가진 노드는 min[H]로 표시됩니다. 위 예시에서 min[H]가 가리키는 값은 4입니다.
피보나치 힙의 활용 분야
피보나치 힙은 특정 알고리즘에서 매우 빠른 성능을 발휘하는 자료구조입니다. 대표적으로 다음과 같은 문제들의 점근적으로(asymptotically) 빠른 알고리즘에서 핵심적인 역할을 합니다.
- 최소 신장 트리(Minimum Spanning Tree, MST) 계산
- 단일 출발점 최단 경로(Single-Source Shortest Path) 탐색
특히 프림(Prim) 알고리즘이나 다익스트라(Dijkstra) 알고리즘과 함께 사용되면, 감소된 키(decrease-key) 연산을 상수 시간에 수행할 수 있어 전체 실행 시간을 크게 단축할 수 있습니다.
참고: 주요 연산의 시간 복잡도
피보나치 힙은 분할상환(amortized) 관점에서 다음과 같은 성능을 제공합니다.
- 삽입(insert), 최솟값 찾기(find-min), 키 감소(decrease-key) : O(1)
- 최솟값 추출(extract-min), 삭제(delete) : O(log n)
- 두 힙의 병합(union) : O(1)
'피보나치'라는 이름은 이러한 시간 복잡도를 분석하는 과정에서 피보나치 수열이 활용되었기 때문에 붙여졌습니다.