피보나치 힙 편집하기

피보나치 힙(Fibonacci heap)은 우선순위 큐를 구현하는 자료구조의 하나로, 삽입과 키 감소 연산이 매우 빠른 것이 특징이다.
==개요==
[[파일:피보나치 힙 예시.png|섬네일|피보나치 힙 구조]]
피보나치 힙은 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.
==각주==
[[분류:자료 구조]]
[[분류:트리]]