피보나치 힙

피보나치 힙(Fibonacci heap)은 우선순위 큐를 구현하는 자료구조의 하나로, 삽입과 키 감소 연산이 매우 빠른 것이 특징이다.

개요

피보나치 힙 구조

피보나치 힙은 1984년 마이클 프레드먼(Michael Fredman)과 로버트 타잔(Robert Tarjan)이 제안한 자료구조로, 이론적으로 매우 효율적인 성능을 제공한다. 특히 삽입, 최소값 찾기, 키 감소 등의 연산이 암묵적으로 상수 시간에 이루어지며, 삭제나 최소값 삭제는 로그 시간 복잡도를 가진다.

구조

피보나치 힙은 여러 개의 트리로 구성된 포레스트(forest) 형태를 갖는다. 각 트리는 최소 힙 속성을 만족하며, 루트 리스트는 이중 연결 리스트로 구현된다. 각 노드는 부모와 자식 노드를 가리키는 포인터를 가지고 있으며, 추가로 마크(mark) 비트를 통해 구조 재구성 시 필요한 정보를 저장한다.

연산

피보나치 힙이 지원하는 주요 연산과 시간 복잡도는 다음과 같다.

• 삽입(Insert): O(1) 암묵적 시간
• 최소값 찾기(Find-Min): O(1)
• 최소값 삭제(Delete-Min): O(log n) 상환 시간
• 키 감소(Decrease-Key): O(1) 상환 시간
• 삭제(Delete): O(log n) 상환 시간
• 합치기(Merge): O(1)

그 구체적인 과정은 다음과 같다.

삽입(Insert)

• 새로운 노드를 생성하여 별개의 트리로 루트 리스트에 삽입한다.

• 삽입 후, 기존 최소 노드와 비교하여 새로운 노드가 더 작으면 최소 노드 포인터를 갱신한다.

• 루트 리스트에 단순히 추가하는 방식이므로 시간 복잡도는 O(1)이다.

최소값 찾기(Find-Min)

• 최소 노드를 가리키는 포인터를 직접 반환한다.

• 힙의 구조를 탐색하거나 변경하지 않으므로 시간 복잡도는 O(1)이다.

합치기(Merge)

• 두 피보나치 힙의 루트 리스트를 단순히 병합한다.

• 두 힙 각각의 최소 노드 포인터 중 더 작은 값을 새로운 최소 노드로 설정한다.

• 포인터 조작만으로 수행되기 때문에 시간 복잡도는 O(1)이다.

키 감소(Decrease-Key)

• 대상 노드의 키 값을 새로운, 더 작은 값으로 갱신한다.

• 갱신된 키가 부모 노드보다 작은 경우:
  • 해당 노드를 잘라 루트 리스트로 이동시킨다.
  • 부모 노드를 검사하여 마크되지 않았다면 마크한다.
  • 이미 마크되어 있다면 부모 노드도 잘라서 루트 리스트로 이동시키고, 이 과정을 조상 노드까지 반복한다(연쇄 절단, Cascading Cut).

• 이 절단 과정은 힙의 평탄화(flattening)를 도와 이후 연산의 효율성을 보장한다.

• 상환 시간 복잡도는 O(1)이다.

삭제(Delete)

• 삭제하려는 노드의 키를 현재 최소 키보다 더 작게 설정한다(Decrease-Key).

• 그런 다음, Delete-Min 연산을 호출하여 해당 노드를 삭제한다.

• Delete-Min을 거쳐야 하므로 시간 복잡도는 O(log n)이다.

최소값 삭제(Delete-Min)

• 현재 최소 노드를 제거한다.

• 제거한 최소 노드의 모든 자식 노드를 루트 리스트에 추가한다. 이때 각 자식 노드는 부모 포인터를 초기화한다.

• 루트 리스트 내에서 동일한 차수(degree)를 가진 트리들을 병합(consolidate)하여 하나의 트리로 만든다.
  • 각 병합은 두 트리의 루트 중 더 작은 키를 가진 것을 새로운 루트로 선택한다.
  • 병합 후 차수는 증가한다.

• 병합이 완료되면, 루트 리스트에서 가장 키가 작은 노드를 새로운 최소 노드로 설정한다.

• 시간 복잡도는 O(log n) (상환)이다.

특징

• 상환 분석을 통해 대부분의 연산에서 매우 낮은 시간 복잡도를 제공한다.
• 다익스트라 알고리즘이나 프림 알고리즘 등에서 성능을 크게 향상시킬 수 있다.
• 이론적으로는 매우 우수하지만, 실제 구현에서는 상수 계수가 커서 일반적인 상황에서는 바이너리 힙보다 느릴 수 있다.

응용

• 최단 경로 알고리즘(다익스트라 알고리즘)
• 최소 신장 트리 알고리즘(프림 알고리즘)
• 다양한 최적화 문제에서 우선순위 큐가 필요한 경우

같이 보기

• 힙 (자료구조)
• 바이너리 힙
• 다익스트라 알고리즘
• 프림 알고리즘
• 상환 분석

참고 문헌

• Michael L. Fredman and Robert E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms," Journal of the ACM (JACM), 1987.