피보나치 힙

**피보나치 힙**(Fibonacci heap) 자료구조는 두 가지 목적으로 사용된다. 첫째는 “병합 가능한 힙”의 몇가지 연산 지원이며, 둘째는 분할 상환을 빈번히 수행하는 응용 프로그램에 매우 적합하도록 상수의 분할 상환 시간을 가지는 것이다. 컴퓨터 과학(computer science)에서 피보나치 힙(Fibonacci heap)은 우선순위 큐(priority queue) 연산을 위한 자료 구조로, 힙-정렬된 트리를 모아놓은 자료 구조이다. 이진 힙(binary heap) 및 이항 힙(binomial heap) 등 다른 많은 우선순위 큐 자료구조에 비해 더 나은 분할 상환된 실행 시간(amortized running time)을 보인다. 피보나치 힙은 Michael L. Fredman과 Robert E. Tarjan이 1984년 개발하였고, 1987년 과학 저널에 발표하였다. 이들은 실행 시간 분석에 피보나치 수가 사용된 것을 따라 피보나치 힙이라 명명하였다. 피보나치 힙에서, 최솟값 탐색(find-minimum) 연산은 분할 상환된 시간이 상수인(O(1)) 만큼 소요된다. 삽입 연산(insert) 및 키 감소 연산(decrease key operation) 또한 상수 분할 상환 시간동안 동작한다. 힙의 크기가 n일때, 구성요소의 삭제는 O(log n) 만큼의 분할 상환 시간이 걸린다. (삭제 연산은 대부분 최소 구성요소를 삭제하는 특수한 경우에 사용된다) 이것은 최대 힙 크기가 n일때, 빈 자료구조부터 시작하여 합쳐서 a개의 삽입연산, 키 감소 연산과 b개의 삭제연산을 임의의 순서대로 수행했을 때 최악의 경우 O(a + b log n) 만큼의 시간이 소요됨을 의미한다. 이진 힙 또는 이항 힙이라면, 이러한 순서의 연산은 O((a + b) log n)의 시간이 소요될 것이다. 그러므로 비상수 요소에 의해 b가 a보다 작을 경우, 피보나치 힙은 이진 힙 또는 이항 힙보다 더 낫다. 두 피보나치 힙을 상수 분할 상환 시간 안에 병합하는 것 또한 가능하다. 이것은 이항 힙의 경우 병합 시간이 O(log n)만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다. 우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에 비해 그래프 내 두 노드 사이의 최단거리를 계산하는 데이크스트라 알고리즘 같은 중요한 알고리즘의 점근적 실행시간을 개선하는 효과를 가져온다.
# 구조
위의 그림에서, (a)에 해당하는 것은 피보나치 힙은 5개의 순서를 갖는 최소힙 트리와 14개의 노드로 이루어져 있으며, 점선은 루트 리스트를 나타낸다. 힙의 최소 노드는 키값 3을 가지고 있으며, 검은색 노드는 마크(mark) 되어 있다. 이런 피보나치 힙의 잠재비용은 5+2*3=11이다. (b) 포인터 p(위쪽 방향 화살표), child(아래쪽 방향 화살표), left와 rifght(왼쪽, 오른쪽 방향 화살표)를 보여주는 좀더 완전한 표현이라 할 수 있다. 피보나치 힙은 최소-힙 특성을 만족시키는 트리들을 모아 놓은 것이다. 즉, 자식의 키는 항상 부모의 키보다 크거나 같다. 이것은 최소 키가 항상 트리들 중 한 트리의 루트에 있다는 것을 의미한다. 이항 힙에 비해, 피보나치 힙의 구조는 좀더 유연하다. 트리는 규정된 모양을 가지지 않는다. 극단적인 경우, 힙의 모든 구성요소가 서로 떨어진 별개의 트리에 존재할 수도 있다. 이러한 유연성으로 인해, 일부 연산은 “게으른” 방식으로 수행할 수 있다. 즉 나중 연산으로 작업을 연기(뒤로 미룸)하는 방식이다. 예를 들어, 힙의 병합(merge)은 두개의 리스트로 구성된 트리를 단순히 결합함으로써 가능하다. 그리고 키 감소 연산(decrease key operation)은 이 노드의 부모로부터 노드를 절단한 후, 새로운 트리를 형성하는 식으로 수행한다. 그러나, 요구되는 실행시간을 달성하기 위해 어느 시점에 어떤 순서가 힙에 도입될 필요가 있다. 특히, 노드의 degree(여기서 degree란 자식의 수를 의미한다)가 상당히 낮게 유지된다. 즉 모든 노드는 degree가 많아야O(log n)이 되며, degree가 k인 노드를 루트로 하는 하위트리의 크기는 적어도Fk+2이다. 여기서Fk 은 k번째 피보나치 수이다. 이것은 루트가 아닌 노드(non-root node)에서는 최대 하나의 자식을 절단할 수 있다는 규칙에 의해 달성된다. 두번째 자식이 절단될 때, 이 노드 자체는 이것의 부모로부터 절단될 필요가 있으며, 이것이 새로운 트리의 루트가 된다. (아래의 Proof of degree bounds 참조). 최솟값 삭제 연산 (delete minimum)을 수행하면 트리의 수가 감소되는데, 이 최솟값 삭제 연산에서 트리가 함께 연결(link) 되기 때문이다. 유연한 구조로 인해 그 결과, 어떤 연산은 긴 시간이 소요될 수 있으나, 반면 다른 연산은 매우 빠르게 수행된다. 분할 상환된 실행시간 분석을 위해, 우리는 잠재비용 방법(potential method)을 사용하였는데, 매우 빠른 연산을 실제 소요되는 시간보다 약간 더 긴 시간이 소요되는 것처럼 하였다. 이때 추가된 시간을 나중에 결합하고, 실제 실행시간에서 감하였다. 잠재비용 함수를 이용하여 이후에 사용을 위해 아껴두었던 시간의 양을 어떤 주어진 시점에 측정한다. 피보나치 힙의 잠재비용은 다음과 같다. Potential = t + 2m 여기서 t는 피보나치 힙 내의 트리 수이며, m 은 표시(mark)된 노드의 수이다. 어떤 노드가 만일 자신의 자식 중 적어도 하나가 절단되었다면 이 노드를 표시(mark)한다. 왜냐하면 이 노드는 다른 노드 (모든 루트는 표시되지 않는다)의 자식으로 만들어졌기 때문이다. 어떤 연산에 대한 분할상환된 시간은 실제 시간과 잠재비용의 차이에 c를 곱한 값을 더하여 구한다. 이때 c는 상수이다 (실제 시간에 대한 O notation에서 매치되는 상수 요소를 찾아 선택한다) 그러므로, 힙 내에서 각 트리의 루트는 한 단위의 시간을 보유(store)하게 된다. 이렇게 보유한 한 단위의 시간을, 나중에 이 트리를 다른 트리에 연결(link)할 때 사용할 수 있다. 그렇게 되면 결국 0 분할상환된 시간 안에 트리를 연결하게 된다. 표시된 각 노드 또한 두 단위의 시간을 보유(store) 한다. 한 단위 시간은 이 노드를 자신의 부모에서 절단할 때 사용할 수 있다. 만일 이 일이 발생하면, 이 노드는 부모가 되고, 나머지 두 번째 시간 단위는 이 노드 안에 여전히 보유한다. 다른 루트 노드가 하나의 시간 단위를 보유한 것처럼 말이다.
# 연산의 구현
삭제와 결합을 빠르게 수행하기 위해, 모든 트리의 루트는 circular, doubly linked 리스트를 사용하여 연결한다. 각 노드의 자식들 또한circular, doubly linked 리스트를 이용해 연결한다. 각 노드 별로, 우리는 이 노드의 자식 노드 수, 그리고 이 노드가 표시된 노드인지 여부를 유지한다. 또한 우리는 최소 키를 포함하고 있는 루트에 대한 포인터를 유지한다.
# 최솟값 찾기
최솟값 찾기 연산은 이제 쉬워지는 것은 최소 키를 가진 루트 노드에 대한 포인터를 유지하기 때문이다. 이것이 힙의 잠재비용을 변경하지는 않는다. 따라서 실제 비용 및 분할상환된 비용 모두 상수(일정한 값)이다. 앞서 언급하였듯이, merge 연산은 두 힙의 트리 루트의 리스트를 결합하여 쉽게 구현 가능하다. 상수 시간 안에 이 연산이 수행될 수 있으며 잠재 비용은 변함없다. 따라서 이것 역시 분할상환 시간을 상수로 만든다.
# 삽입
삽입 연산은 하나의 구성요소를 가지고 새로운 힙을 생성한 후, 병합함으로써 수행된다. 이러한 삽입 연산에는 상수 시간이 소요되며, 잠재비용은 1만큼 증가하는데, 트리의 수가 증가되기 때문이다. 분할상환된 비용은 그러므로 여전히 상수이다. 삽입의 좀더 상세한 그림은 아래와 같다. (a)의 피보니차 힙 H가 있으며 (b)키가 21인 노드를 삽입한 후의 피보나치 힙 H이다. 노드 하나로 이루어진 최소힙 순서를 가진 트리가 되고, 루트의 리스트에 더해져 루트의 왼쪽 형제 노드가 된다. 의사코드는 아래와 같다.
1 degree[x] 0
2 p[x] NIL
3 child[x] NIL
4 left[x] x
5 right[x] x
6 mark[x] FALSE
7 concatenate the root list containing x with root list H
8 if min[H] = NIL or key[x] 0라고 하자. y1, y2, ..., yd는 x의 자식이고, x의 자식으로 최근 생성된 순서대로 인덱스되었다. (즉 y1 은 가장 오래전 것, yd 은 가장 최근 것), c1, c2, ..., cd 은 각각의 degree라고 한다. 우리는2≤i≤d인 각 i에 대해ci ≥ i-2 라고 주장한다. yi이 x의 자식으로 생성되기 바로 전, y1,...,yi−1 은 이미 x의 자식이다. 그러니 x는 이 시점에 적어도 i-1 의 degree를 가졌다. 트리의 루트들이 degree가 동일할 때에만 트리들은 결합되므로, 이것이 x의 자식이 되는 시점에만 yi는 적어도 i-1의 degree를 가진다. 이 시점에서부터 현재까지, yi는 최대한 하나의 자식을 잃을 수 있다 (이것은 marking 과정에 의해 보장된다). 그래서 이것의 현재 degree인 ci 은 적어도i−2이다. 이로써 이 주장이 증명되었다. 모든yi 의 높이가 x의 높이보다 엄격하게 더 작으므로, 우리는 이 귀납적 가정을\textbf{size}(x) \ge 2 + \sum_{i=2}^d \textbf{size}(y_i) \ge 2 + \sum_{i=2}^d F_i = 1 + \sum_{i=0}^d F_i. 을 구하기 위하여 이들에 적용할 수 있다. 노드x 와 y1는 각각 적어도 1을size(x)에 기여한다. 그래서 우리는 다음을 얻는다.
# 최악의 경우
피보나치 힙이 매우 효율적인 것처럼 보이기는 하지만, 다음과 같은 두 단점이 있다 (“Pairing Heap: A new form of Self Adjusting Heap”이라는 논문에서 언급한대로). “피보나치 힙은 코딩하기에는 복잡하다. 또한 이론적으로는 덜 효율적인 다른 형태의 힙들에 비해 실제적으로는 그렇게 효율적이지 않은데, 가장 단순한 버전 조차도, 다른 구조체가 노드 당 두개 또는 세개의 포인터를 요구하는데 비해, 노드 별로 네 개의 포인터를 유지하기 위한 저장공간과 조작이 필요하기 때문이다.” 이러한 다른 구조체는 이진 힙, 이항 힙, Pairing Heap, Brodal Heap, Rank Pairing Heap 등을 일컫는다. 빈 자료구조에서부터 시작해서 몇 개의 연산을 순차적으로 수행하는데 걸리는 전체 실행시간은 위에서 계산하였던 경계값 내에서 그 범위가 정해지기는 하지만, 이 순차 수행하는 연산 중 일부 연산 (매우 적기는 하지만)은 완료하는데 매우 오랜 시간이 소요될 수 있다 (특히, 삭제연산 및 최솟값 삭제연산은 최악의 경우 실행하는데 선형 시간(linear time)이 소요된다). 이러한 이유로 피보나치 힙과 다른 분할상환된 자료 구조는 실시간 시스템에는 적합하지 않을 수 있다. 최악의 경우의 성능이, 피보나치가 가지는 분할상환 성능과 동일한 자료 구조를 새로 만드는 것이 가능하다. 그러한 구조 중 하나가 Brodal queue인데, 이것을 창안한 창안자의 말을 빌리자면 “상당히 복잡한” 그리고 “현실적으로는 응용가능하지 않을” 구조라고 하였다. 2012년에 만들어진 엄격한 피보나치 힙은 동일한 최악의 경우의 경계값을 가지는 보다 단순한 구조이다 (Brodal의 것에 비하면 그렇다) 이 보다 엄격한 피보나치 힙이 실제로 적용했을 때 효율적인지 여부는 알려지지 않았다. 실행에서 다소 유연한 Driscoll et al.의 힙은 merge를 제외한 나머지 연산에 대해 피보나치 힙보다 보다 나은 최악 경우의 성능을 보였다.
# 수행시간
다음의 시간 복잡도는 Binary Heap, Binomial Heap, Fibonacci Heap에 대해서만 나타난 것이다. {| class="wikitable" |- ! !! Binary heap !! Binomial heap !! Fibonacci heap |- | MAKE-HEAP || Θ(1) || Θ(1) || Θ(1) |- | INSERT || Θ(lg n) || O(lg n) || Θ(1) |- | MINIMUM || Θ(1) || O(lg n) || Θ(1) |- | EXTRACT-MIN || Θ(lg n) || Θ(lg n) || O(lg n) |- | UNION || Θ(n) || O(lg n) || Θ(1) |- | DECREASE-KEY || Θ(lg n) || Θ(lg n) || Θ(1) |- | DELETE || Θ(lg n) || Θ(lg n) || O(lg n) |}