피보나치 힙

피보나치 힙(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] < key[min[H]]
9 then min[H] x
10 n[H] n[H] + 1
1-4행에서는 노드 x의 구조적인 속성들의 일부를 초기화하며, 5행에서는 피보나치 힙 H가 비어 있는지를 검사한다. 만약 비었다면 6~7행에서 x를 H의 루트 리스트에서 유일한 노드로 만들고 min[H]가 x를 가리키도록 지정한다. 비어 있지 않으면 8~10행에서 x를 H의 루트 리스트에 삽입하고 필요하다면 min[H]을 변경한다. 마지막으로 11행에서 새로운 노드의 추가를 반영하기 위해 n[H]를 증가 시킨다.

최소값 추출[편집]

최소값 추출 연산 (Operation extract minimum)(최소값 삭제와 동일) 세 단계로 수행된다. 첫번째, 우리는 최소 값을 가진 루트를 꺼내 제거한다. 이것의 자식들은 새로운 트리의 루트들이 된다. 만일 자식의 수가 d라면, 모든 새로운 루트를 처리하는데O(d)의 시간이 소요되며, 잠재비용은 d-1 만큼 증가한다. 그러므로 이 단계에서의 분할상환 실행시간은O(d) = O(log n)이다. 최소값 추출 연산을 완료하기 위해서는, 마지막으로 최소 키를 가진 루트를 가리키는 포인터를 업데이트 해야 한다. 불행히도 우리가 체크해야 할 루트는 최대 n개가 될 수도 있다. 두번째 단계에서 그러므로 동일한 degree를 가진 루트들을 서로 연결하여 루트의 수를 감소시킨다. 두 루트인 u와 v 가 동일한 degree를 가진다면, 더 작은 키를 가진 것이 루트가 될 수 있도록 하여 둘 중 하나를 나머지 트리의 자식으로 만든다. 그러면 degree는 1 증가할 것이다. 이러한 작업은 모든 루트의 degree가 서로 다를 때까지 반복한다. 동일한 degree를 가지는 트리를 효율적으로 찾기 위하여, 우리는 길이가O(log n)인 어레이를 사용한다. 이 어레이 내에 각 degree 별로 루트를 가리키는 포인터를 저장한다. 두번째 루트가 동일한 degree인 것을 발견하면, 이 두 개의 트리를 연결하고, 어레이를 업데이트한다. 실제 실행시간은O(log n + m)이다. 여기서 m은 두번째 단계를 시작한 시점에서의 루트의 수이다. 마지막에 결국 우리는 최대O(log n) 만큼의 루트를 가지게 된다. (왜냐하면 각각은 서로 다른 degree를 가질 것이기 때문임) 그러므로, 이 단계의 전과 후 잠재비용 함수의 차이는: O(log n) − m, 또한 분할상환된 실행 시간은 최대O(log n + m) + c(O(log n) − m)이다. 충분히 큰 c값을 선택하면, 이것은O(log n)으로 단순화된다. 세번째 단계에서 우리는 남은 루트 각각을 체크하여 최소값을 찾는다. 이것에O(log n)만큼의 시간이 소요되며, 잠재비용은 변함없다. 최소 추출 연산의 전체적인 분할상환 실행시간은 그러므로 O(log n)이다. 글만으로 이해하기 어려울 것 같아 아래의 그림으로 상세하게 설명하면 아래와 같다.

먼저 (a)의 피보나치 힙에서 (b)의 루트 리스트에서 최소 노드 z를 제거하고 그 자식들을 루트 리스트에 추가한 후의 모습이다. (c)에서 (e)는 H.min이 가리키는 노드에서 시작하고 그 right 포인터들을 따라가면서 루트 리스트를 처리한다. 각 부분은 각 반복의 끝에서의 w와 x값을 보여준다. (f)는 키 값이 23s인 노드는 현재 x가 가리키는 키값이 7인 노드에 연결되어 있고, (g)에서 키값이 17인 노드는 여전히 x가 가리키는 키 값이 7인 노드에 연결되었다. (h)에서 키값이 24인 노드가 키값이 7인 노드에 연결되어 있으며, A[3]이 가리키는 노드가 없어 이 결과로 생성되는 트리의 루트를 가리키도록 설정된다. 이와 마찬가지로 (i) ~ (m)의 과정을 수행하면 위의 그림과 같다. 이는 루트리스트의 모든 루트가 서로 다른 유일한 차수를 가질 때까지 반복적으로 수행된다.

키 감소[편집]

키 감소 연산 (Operation decrease key)은 노드를 취하여 키를 감소시킨다. 이로 인해 힙의 특성이 위반되었다면 (새로운 키가 부모의 키보다 작다), 이 노드를 부모로부터 절단한다. 만일 부모가 루트가 아니면, 이 노드를 표시한다. 만일 이 노드가 이미 표시된 것이라면, 이것을 절단하고 부모를 표시한다. 이 과정을 반복하면서 위로 올라가는데, 루트 또는 표시되지 않은 노드를 만날 때까지 계속한다. 이것이 새로운 최소값이라면, 이제 최소값 포인터를 감소된 값으로 설정한다. 이 과정에서 우리는 신규 트리를 생성한다. (이때 이 신규 트리의 수를 k라 하자). 첫번째 트리를 제외한 신규 생성된 트리 각각은 원래 표시된 것이었겠으나, 루트로는 표시되지 않은 (unmarked) 것이 된다. 하나의 노드는 marked될 수 있다. 그러므로, 표시된 노드의 수는 −(k − 1) + 1 = − k + 2 만큼 변경된다. 두 변경을 결합하면, 잠재 비용은 2(−k + 2) + k = −k + 4만큼 변경된다. 절단을 수행하는데 소요되는 실제 시간은O(k)이었으므로, (다시 한번 충분히 큰 c값을 선택하면) 분할상환된 실행 시간은 상수이다. 마지막으로, 삭제 연산(operation delete)은 삭제하고자 하는 구성요소의 키를 무한대로 마이너스하여 감소시킨다. 이렇게 하여 이 노드를 전체 힙에서 최소값을 보유한 노드가 되게 한다. 이제 최소값 추출 함수를 호출하여 이것을 찾아 제거한다. 이 연산의 분할상환된 실행시간은 O(log n)이다. 아래의 그림으로 더 자세하게 설명하겠다

(a)의 피보나치 힙에서 (b)의 46을 키로가지는 노드는 키가 15로 감소했으며, 그 노드는 루트가 되고 마크가 되지 않았던(24를 키로가지는)부모는 마크가 되었다. (c)~(e) 35의 키를 가지는 노드는 키가 5로 감소했다. (c)에서 그 노드는 5를 키로 가지는 루트가 되었다. 26을 키로 가지는 부모는 마크되어 있어 연속적인 분리가 발생한다. 26을 키로 가지는 노드는 부모로부터 분리되고 마크가 안된 루트가 (d)에서 된다. 또 24를 키로 가지는 노드가 마크되어 있으므로, 다시 연속적인 분리가 발생한다. 이 노드는 그의 부모로부터 분리되고 마크가 안된 루트가 (e)에서 된다. 7을 키로 갖는 노드가 루트므로 연속적인 분리는 여기서 멈추게 된다.

Degree 경계의 증명[편집]

피보나치 힙의 분할상환된 성능은 임의의 트리 루트의 degree(자식 노드의 수), 즉O(log n)에 따라 달라지는데, 여기서n 은 힙의 크기이다.

여기서 우리는 힙 내에서 degree가 d인 임의의 노드 x를 루트로 하는 (하위)트리의 크기는 적어도F_d+2가 되어야만 한다. 여기서F_k 은 k번째 피보나치 수이다.

Degree 경계는 이것부터 시작하여 다음의 사실, 그러니까 d≥0 인 모든 정수에 대해 $F_{d+2}\geq \varphi ^{d}$ (유도를 통해 쉽게 증명됨)를 따른다. 여기서 φ=((1+√5))⁄2=1.618이다. (그리고서 우리는 $n\geq F_{d+2}\geq \varphi ^{d}$ 을 가지며, 양 변에 기초가 φ 인 로그를 취하면 d≤〖log〗_φ n 을 얻는다).

임의의 노드 x가 힙 내 어느 곳에 존재한다고 하면 (x는 메인 트리 중 하나의 루트 노드일 필요는 없다). size(x)는 x (x 자신을 포함하여 x의 자손의 수)를 루트로 하는 트리의 크기로 정의하자. 우리는 높이 x (x로부터 자손 leaf까지 도달하는 가장 긴 단순 트리의 길이)에 대해size(x) ≥ F_d+2 임을 증명한다. 여기서 d는 x의 degree이다.

기초 사례: 만일 x가 높이 0을 가진다면, d=0이고size(x) = 1 = F2. 귀납적 사례: x가 양의 높이를 가졌고, degree d>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)\geq 2+\sum _{i=2}^{d}{\textbf {size}}(y_{i})\geq 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에 대해서만 나타난 것이다.

	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)

참고 문헌[편집]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 19: Binomial Heaps, pp. 455?475.
Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309?314.