##이다. 이러한 작업은 모든 루트의 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 ) ( log n ) - m ) 이다. 충분히 큰 c값을 선택하면, 이것은O ( log n ) 으로 단순화된다. 세번째 단계에서 우리는 남은 루트 각각을 체크하여 최소값을 찾는다. 이것에O ( log n ) 만큼의 시간이 소요되며, 잠재비용은 변함없다. 최소
##를 가지는 노드는 키가 5로 감소했다. 에서 그 노드는 5를 키로 가지는 루트가 되었다. 26을 키로 가지는 부모는 마크되어 있어 연속적인 분리가 발생한다. 26을 키로 가지는 노드는 부모로부터 분리되고 마크가 안된 루트가 ( d ) 에서 된다. 또 24를 키로 가지는 노드가 마크되어 있으므로, 다시 연속적인 분리가 발생한다. 이 노드는 그의 부모로부터 분리되고 마크가 안된 루트가 ( e ) 에서 된다. 7을 키로 갖는 노드가 루트므로 연속적인 분리는 여기서 멈추게 된다. Degree 경계의 증명 [ 편집 ] 피보나치 힙의 분할상환된 성능은 임의의 트리 루트의 degree ( 자식 노드의 수 ), 즉O ( log n ) 에 따라 달라지는데, 여기서n 은 힙의 크기이다. 여기서 우리는 힙 내에서 degree가 d인 임의의 노드 x를 루트로 하는 ( 하위 ) 트리의 크기는 적어도Fd2가 되어야만 한다. 여기서Fk 은 k번째 피보나치 수이다. Degree 경계는 이것부터 시작하여 다음의 사실, 그러니까 인 모든 정수에 대해 F d 2 d { displaystyle F - { d2 } geq
##의 루트를 가리키도록 설정된다. 이와 마찬가지로 ( i ) ~ ( m ) 의 과정을 수행하면 위의 그림과 같다. 이는 루트리스트의 모든 루트가 서로 다른 유일한 차수를 가질 때까지 반복적으로 수행된다. 키 감소 [ 편집 ] 키 감소 연산 ( Operation decrease key ) 은 노드를 취하여 키를 감소시킨다. 이로 인해 힙의 특성이 위반되었다면 ( 새로운 키가 부모의 키보다 작다 ), 이 노드를 부모로부터 절단한다. 만일 부모가 루트가 아니면, 이 노드를 표시한다. 만일 이 노드가 이미 표시된 것이라면, 이것을 절단하고 부모를 표시한다. 이 과정을 반복하면서 위로 올라가는데, 루트 또는 표시되지 않은 노드를 만날 때까지 계속한다. 이것이 새로운 최소값이라면, 이제 최소값 포인터를 감소된 값으로 설정한다. 이 과정에서 우리는 신규 트리를 생성한다. ( 이때 이 신규 트리의 수를 k라 하자 ). 첫번째 트리를 제외한 신규 생성된 트리 각각은 원래 표시된 것이었겠으나, 루트로는 표시되지 않은 ( unmarked ) 것이 된다. 하나의 노드는 marked될 수 있다. 그러므로, 표시된 노드의 수는 - ( k - 1 )
최소값을 찾는다. 이것에O ( log n ) 만큼의 시간이 소요되며, 잠재비용은 변함없다. 최소 추출 연산의 전체적인 분할상환 실행시간은 그러므로 O ( log n ) 이다. 글만으로 이해하기 어려울 것 같아 아래의 그림으로 상세하게 설명하면 아래와 같다. 먼저 ( a ) 의 피보나치 힙에서 ( b ) 의 루트 리스트에서 최소 노드 z를 제거하고 그 자식들을 루트 리스트에 추가한 후의 모습이다. 에서 ( e ) 는 H. min이 가리키는 노드에서 시작하고 그 right 포인터들으ㄹ 따라가면서 루트 리스트를 처리한다. 각 부분은 각 반복의 끝에서의 w와 x값을 보여준다. ( f ) 는 키 값이 23s인 노드는 현재 x가 가리키는 키값이 7인 노드에 연결되어 있고, ( g ) 에서 키값이 17인 노드는 여전히 x가 가리키는 키 값이 7인 노드에 연결되었다. ( h ) 에서 키값이 24인 노드가 키값이 7인 노드에 연결되어 있으며, A [ 3 ] 이 가리키는 노드가 없어 이 결과로 생성되는 트리의 루트를 가리키도록 설정된다. 이와 마찬가지로 ( i ) ~ ( m ) 의 과정을 수행하면 위의 그림과 같다
##드를 삽입한 후의 피보나치 힙 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 ] 를 증가 시킨다. 최소값 추출 [ 편집 ] 최소값 추출
##다. 두 피보나치 힙을 상수 분할 상환 시간 안에 병합하는 것 또한 가능하다. 이것은 이항 힙의 경우 병합 시간이 O ( log n ) 만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다. 우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에 비해 그래프 내 두 노드 사이의 최단거리를 계산하는 데이크스트라 알고리즘 같은 중요한 알고리즘의 점근적 실행시간을 개선하는 효과를 가져온다. 목차 1 구조 2 연산의 구현 3 최소값 찾기 4 삽입 5 최소값 추출 6 키 감소 7 Degree 경계의 증명 8 최악의 경우 9 수행시간 10 참고문헌 구조 [ 편집 ] 위의 그림에서, ( a ) 에 해당하는 것은 피보나치 힙은 5개의 순서를 갖는 최소힙 트리와 14개의 노드로 이루어져 있으며, 점섬은 루트 리스트를 나타낸다. 힙의 최소 노드는 키값 3을 가지고 있으며, 검은색 노드는 마크 ( mark ) 되어 있다. 이런 피보나치 힙의 잠재비용은 52 * 3 = 11이다. ( b ) 포인터 p ( 위쪽 방향 화살표 ), child
된다. 하나의 노드는 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를 키로가지는 ) 부모는 마크가 되었다. ~ ( e ) 35의 키를 가지는 노드는 키가 5로 감소했다. 에서 그 노드는 5를 키로 가지는 루트가 되었다.
##다 ( " Pairing Heap : A new form of Self Adjusting Heap " 이라는 논문에서 언급한대로 ). " 피보나치 힙은 코딩하기에는 복잡하다. 또한 이론적으로는 덜 효율적인 다른 형태의 힙들에 비해 실제적으로는 그렇게 효율적이지 않은데, 가장 단순한 버전 조차도, 다른 구조체가 노드 당 두개 또는 세개의 포인터를 요구하는데 비해, 노드 별로 네 개의 포인터를 유지하기 위한 저장공간과 조작이 필요하기 때문이다. " 이러한 다른 구조체는 이진 힙, 이항 힙, Pairing Heap, Brodal Heap, Rank Pairing Heap 등을 일컫는다. 빈 자료구조에서부터 시작해서 몇 개의 연산을 순차적으로 수행하는데 걸리는 전체 실행시간은 위에서 계산하였던 경계값 내에서 그 범위가 정해지기는 하지만, 이 순차 수행하는 연산 중 일부 연산 ( 매우 적기는 하지만 ) 은 완료하는데 매우 오랜 시간이 소요될 수 있다 ( 특히, 삭제연산 및 최소값 삭제연산은 최악의 경우 실행하는데 선형 시간 ( linear time ) ( linear time ) 이 소요된다 ). 이러한 이유로 피보나치 힙과 다른 분할상환된 자료 구조는 실시간 시스템에는 적합하지 않을 수 있다
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. 455475. Vuillemin, J. ( 1978 ). A data structure for manipulating priority queues. Communications of the ACM 21
##으로 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를 가지는 트리
피보나치 힙(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)(1)) 만큼 소요된다. 삽입 연산(insert) 및 키 감소 연산(decrease key operation) 또한 상수 분할 상환 시간동안 동작한다. 힙의 크기가 n일때, 구성요소의 삭제는 O(log n) 만큼의 분할 상환 시간이 걸린다. (삭제 연산은 대부분 최소 구성요소를 삭제하는 특수한 경우에 사용된다) 이것은 최대 힙 크기가 n일때, 빈 자료구조부터 시작하여 합쳐서 a개의 삽입연산, 키 감소 연산과 b개의 삭제연산을 임의의 순서대로 수행했을 때 최악의 경우 O(a b log n) 만큼의 시간이 소요됨을 의미한다. 이진 힙 또는 이항 힙이라면, 이러한 순서의 연산은 O((a b)(a b) log n)의 시간이 소요될 것이다. 그러므로 비상수 요소에 의해 b가 a보다 작을 경우, 피보나치 힙은 이진 힙 또는 이항 힙보다 더 낫다. 두 피보나치 힙을 상수 분할 상환 시간 안에 병합하는 것 또한 가능하다. 이것은 이항 힙의 경우 병합 시간이 O(log n)만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다. 우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에 비해 그래프 내 두 노드 사이의 최단거리를 계산하는 데이크스트라 알고리즘 같은 중요한 알고리즘의 점근적 실행시간을 개선하는 효과를 가져온다.