피보나치 힙 (Fibonacci heap)

한 줄 정의: 여러 개의 트리로 이루어진 느슨한 구조를 가지며, 삽입과 최솟값 감소(decrease-key) 연산을 상환 상수 시간에 지원하도록 설계된 힙 자료구조.

쉽게 풀면

피보나치 힙은 일반적인 이진 힙보다 더 정교한 구조를 가진 힙으로, 여러 개의 작은 트리 뭉치를 느슨하게 관리한다. 특히 '이미 힙에 있는 원소의 우선순위를 더 낮게 바꾸는' decrease-key 연산을 매우 빠르게(상환 상수 시간에) 처리할 수 있다는 점이 특징이다. 이 성질 덕분에 다익스트라 알고리즘이나 프림 알고리즘 같은 그래프 알고리즘의 이론적 시간 복잡도를 최적화하는 데 사용된다.

왜 중요한가

피보나치 힙은 decrease-key 연산을 상환 상수 시간에 처리할 수 있다는 점에서, 최단경로나 최소 신장 트리처럼 우선순위가 계속 갱신되는 그래프 알고리즘의 이론적 시간 복잡도를 최적으로 끌어올리는 데 결정적인 역할을 합니다. 이 때문에 알고리즘 이론 논문에서는 새로운 알고리즘의 점근적 상한을 증명할 때 자료구조 선택의 근거로 자주 인용되며, 상각 분석(amortized analysis) 기법을 설명하는 대표 사례로도 널리 쓰입니다.

논문에서는 이렇게 쓰입니다

"피보나치 힙을 사용한 다익스트라 알고리즘의 시간 복잡도는 O(E + V log V)로, 이진 힙을 사용할 때보다 이론적으로 개선된다."

그래프 알고리즘의 점근적 시간 복잡도를 더욱 최적화하기 위한 고급 자료구조 선택을 설명할 때 쓰인다.

"프림 알고리즘에서 피보나치 힙을 우선순위 큐로 채택하여 간선 수에 대한 의존성을 줄인 최소 신장 트리 구성법을 제시하였다."

최소 신장 트리를 구하는 프림 알고리즘에서도 정점의 우선순위를 계속 갱신해야 하므로, 이 갱신 연산이 빠른 피보나치 힙을 사용해 전체 알고리즘의 이론적 성능을 개선했다는 뜻입니다.

"네트워크 흐름 최적화 문제를 다루면서 피보나치 힙 기반 자료구조의 상각 비용 분석을 통해 알고리즘의 점근적 복잡도 상한을 증명하였다."

실제 실행 시간이 아니라 여러 연산에 걸친 평균적 비용(상각 비용)을 수학적으로 증명하는 데 피보나치 힙을 예시로 사용한 서술로, 이론 전산학 논문에서 자주 등장하는 분석 방식입니다.

조금 더 깊게 보면

피보나치 힙의 핵심은 삽입이나 최솟값 감소 연산을 즉시 정리하지 않고 느슨하게 쌓아두었다가, 최솟값을 꺼낼 때(extract-min)에만 트리들을 합치는 정리 작업을 몰아서 처리한다는 점입니다. 이 "게으른" 처리 방식 덕분에 개별 연산은 느릴 수 있어도 여러 번의 연산에 걸쳐 평균을 내면(상각 분석) 매우 효율적이라는 결론이 나오며, 이 증명에는 각 노드의 자식 수 상한이 피보나치 수열과 관련된다는 점(이름의 유래)이 사용됩니다. 다만 실제 구현에서는 포인터 조작이 많고 상수 계수가 커서, 이론적 우수성이 실무 성능으로 그대로 이어지지는 않는다는 점이 흔히 함께 언급됩니다.

주의할 점

피보나치 힙은 이론적 시간 복잡도는 우수하지만 구현이 복잡하고 상수 계수가 커서, 실제로는 단순한 이진 힙이 더 빠른 경우가 많아 실무에서는 잘 쓰이지 않는다.