피보나치 힙(Fibonacci heap)은 컴퓨터 과학에서 우선순위 큐(priority queue) 연산을 구현하기 위해 사용되는 자료구조이다. 최소 힙 성질(min-heap property)을 만족하는 트리들의 집합으로 구성되며, 1984년 마이클 프레드먼(Michael L. Fredman)과 로버트 타잔(Robert E. Tarjan)이 제안하고 1987년 학술지에 발표하였다.
이 자료구조는 병합 가능한 힙(mergeable heap)의 여러 연산을 지원하며, 특히 분할 상환 시간(amortized time) 측면에서 이진 힙(binary heap)이나 이항 힙(binomial heap)보다 우수한 성능을 보인다. 삽입(insert), 최솟값 찾기(find-min), 키 감소(decrease-key), 병합(merge) 연산은 상수 시간의 분할 상환 복잡도를 가지며, 최솟값 삭제(delete-min)는 O(log n)의 분할 상환 시간이 소요된다.
피보나치 힙이라는 명칭은 이 자료구조의 시간 복잡도 분석에서 피보나치 수열(Fibonacci numbers)이 사용되기 때문에 붙여졌다. 구체적으로, 차수(degree)가 k인 노드를 루트로 하는 부분 트리의 크기는 최소한 F(k+2) 이상이라는 성질이 성립하며, 여기서 F(i)는 i번째 피보나치 수이다. 이러한 구조적 제약 덕분에 각 노드의 차수가 O(log n)으로 유지된다.
주요 응용 분야로는 그래프 알고리즘이 있다. 피보나치 힙을 사용하면 다익스트라(Dijkstra) 알고리즘과 프림(Prim) 알고리즘의 점근적 실행 시간을 O(|E| + |V| log |V|)로 개선할 수 있다.
그러나 피보나치 힙은 구현이 복잡하고, 실제 실행 환경에서는 이론적으로 덜 효율적인 다른 힙 자료구조에 비해 성능이 떨어지는 경우가 많다는 한계점이 있다. 각 노드당 네 개의 포인터를 관리해야 하므로 메모리 소비가 크고 모든 연산의 상수 계수가 높기 때문이다. 또한 분할 상환 분석에 기반하므로 실시간 시스템과 같이 최악의 경우 실행 시간이 제한되어야 하는 환경에는 적합하지 않을 수 있다. 이와 같은 이유로 실제 응용에서는 이론적 우수성에도 불구하고 피보나치 힙보다 구현이 단순한 페어링 힙(pairing heap) 등이 더 널리 사용되기도 한다.
피보나치 힙의 최악의 경우 성능을 갖는 자료구조로는 브로달 큐(Brodal queue, 1996)와 스트릭트 피보나치 힙(strict Fibonacci heap, 2012) 등이 연구된 바 있다.
