피보나치 힙

피보나치 힙 (Fibonacci heap)은 컴퓨터 과학에서 사용하는 힙 자료 구조의 일종으로, 특히 합병 연산이 빈번하게 발생하는 경우에 매우 효율적인 성능을 보인다. 1984년에 마이클 프레드먼(Michael L. Fredman)과 로버트 타잔(Robert E. Tarjan)에 의해 개발되었다.

피보나치 힙은 이진 힙이나 이항 힙과 같은 다른 힙 구현체에 비해 몇몇 연산에서 더 나은 상환 시간 복잡도(amortized time complexity)를 제공한다. 특히 다음 연산들이 그러하다:

• 삽입 (Insert): O(1)
• 최소값 찾기 (Find-Minimum): O(1)
• 최소값 삭제 (Extract-Minimum): O(log n) (n은 힙의 크기)
• 합병 (Union): O(1)
• 키 감소 (Decrease-Key): O(1)
• 삭제 (Delete): O(log n)

여기서 O(1)은 상환 시간 복잡도이며, 실제로는 여러 연산에 걸쳐 비용이 분산되어 나타날 수 있다.

피보나치 힙은 힙 순서 속성을 만족하는 트리들의 집합으로 구성된다. 각 노드는 키 값을 가지고 있으며, 부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같다 (최소 힙 기준). 피보나치 힙의 중요한 특징은 "표시(mark)"된 노드의 존재이다. 노드가 자식 노드를 잃게 되면, 그 노드는 "표시"된다. 만약 표시된 노드가 또 다른 자식 노드를 잃게 되면, 그 노드는 부모 노드에서 잘려져 나와 새로운 트리의 루트가 된다. 이러한 잘라내기(cut) 연산은 힙의 구조를 유지하고 성능을 보장하는 데 중요한 역할을 한다.

피보나치 힙은 이론적으로는 매우 효율적이지만, 실제로 구현했을 때 다른 힙 구조에 비해 복잡하고, 숨겨진 상수 요소가 클 수 있기 때문에, 실제 사용 빈도는 높지 않다. 하지만 다익스트라 알고리즘(Dijkstra's algorithm)이나 최소 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘과 같은 특수한 그래프 알고리즘에서 성능 향상을 위해 사용될 수 있다.