피보나치 힙은 그래프 알고리즘과 같이 최소 힙 및 최대 힙을 유지하는 데 사용되는 특별한 유형의 힙 데이터 구조입니다. 피보나치 힙은 결합, 삭제 및 감소 동작에서 매우 빠른 속도를 제공합니다. 이 데이터 구조는 흔히 그래프 알고리즘과 최단 경로 알고리즘에서 사용됩니다.

피보나치 힙의 구조

피보나치 힙은 트리 구조로 구성되어 있습니다. 각 노드는 이진 트리가 아니라 다른 노드에 대한 포인터 목록을 가지고 있습니다. 이로 인해 힙을 유지하고 조작하는 데 필요한 복잡도가 낮아집니다.

피보나치 힙에는 다음과 같은 주요 속성이 있습니다:

1. 각 노드는 부모, 왼쪽 자식, 오른쪽 자식, 이전 노드 및 다음 노드에 대한 포인터를 가집니다.
2. 힙의 모든 노드는 서로 다른 차수(자식의 수)를 가집니다.
3. 모든 노드의 자식을 끊어내었을 때 해당 노드는 루트 목록에 추가됩니다.
4. 최솟값 노드는 힙의 루트 목록에 직접적으로 연결되어 있습니다.

피보나치 힙의 연산

피보나치 힙은 다음과 같은 주요 연산을 지원합니다:

• 결합(Union): 두 개의 피보나치 힙을 하나의 피보나치 힙으로 결합합니다.
• 최솟값 추출(Find Minimum): 최솟값 노드를 찾아 반환합니다.
• 노드 삽입(Insert Node): 새로운 노드를 삽입합니다.
• 최솟값 삭제(Delete Minimum): 최솟값 노드를 힙에서 제거하고 해당 노드의 자식들을 새로운 루트 목록에 추가합니다.
• 노드 감소(Decrease Key): 해당 노드의 값을 감소시켜 힙 조건을 유지합니다.

피보나치 힙의 성능

피보나치 힙은 다음과 같은 성능을 제공합니다:

• 결합, 삭제, 최솟값 추출, 노드 삽입, 노드 감소 등의 연산을 모두 $O(1)$의 평균 시간 복잡도로 수행할 수 있습니다.

피보나치 힙은 효율적인 연산 및 빠른 성능을 제공하여 그래프 알고리즘과 최단 경로 알고리즘과 같은 다양한 응용 분야에서 널리 사용됩니다.

참고: Fibonacci Heap - Wikipedia