피보나치 힙 - 위키백과, 우리 모두의 백과사전 피보나치 힙 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 피보나치 힙 ( Fibonacci heap ) 자료구조는 두 가지 목적으로 사용된다. 첫째는 " 병합 가능한 힙 " 의 몇가지 연산 지원이며, 둘째는 분할 상환을 빈번히 수행하는 응용 프로그램에 매우 적합하도록 상수의 분할 상환 시간을 가지는 것이다. 컴퓨터 과학 ( computer science ) 에서 피보나치 힙 ( Fibonacci heap ) 은 우선순위 큐 ( priority queue ) 연산을 위한 자료 구조로, 힙 - 정렬된 트리를 모아놓은 자료 구조이다. 이진 힙 ( binary heap ) 및 이항 힙 ( binomial heap ) 등 다른 많은 우선순위 큐 자료구조에 비해 더 나은 분할
구조로, 힙 - 정렬된 트리를 모아놓은 자료 구조이다. 이진 힙 ( binary heap ) 및 이항 힙 ( binomial heap ) 등 다른 많은 우선순위 큐 자료구조에 비해 더 나은 분할 상환된 실행 시간 ( amortized running time ) 을 보인다. 피보나치 힙은 Michael L. Fredman과 Robert E. Tarjan이 1984년 개발하였고, 1987년 과학 저널에 발표하였다. 이들은 실행 시간 분석에 피보나치 수가 사용된 것을 따라 피보나치 힙이라 명명하였다. 피보나치 힙에서, 최솟값 탐색 ( find - minimum ) 연산은 분할 상환된 시간이 상수인 ( O ( 1 ) ( 1 ) ) 만큼 소요된다. 삽입 연산 ( insert ) 및 키 감소 연산 ( decrease key operation
( 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 ) l
ge ) 은 두개의 리스트로 구성된 트리를 단순히 결합함으로써 가능하다. 그리고 키 감소 연산 ( decrease key operation ) 은 이 노드의 부모로부터 노드를 절단한 후, 새로운 트리를 형성하는 식으로 수행한다. 그러나, 요구되는 실행시간을 달성하기 위해 어느 시점에 어떤 순서가 힙에 도입될 필요가 있다. 특히, 노드의 degree ( 여기서 degree란 자식의 수를 의미한다 ) 가 상당히 낮게 유지된다. 즉 모든 노드는 degree가 많아야O ( log n ) 이 되며, degree가 k인 노드를 루트로 하는 하위트리의 크기는 적어도Fk2이다. 여기서Fk 은 k번째 피보나치 수이다. 이것은 루트가 아닌 노드 ( non - root node ) 에서는
는 것은 최소 키를 가진 루트 노드에 대한 포인터를 유지하기 때문이다. 이것이 힙의 잠재비용을 변경하지는 않는다. 따라서 실제 비용 및 분할상환된 비용 모두 상수 ( 일정한 값 ) 이다. 앞서 언급하였듯이, merge 연산은 두 힙의 트리 루트의 리스트를 결합하여 쉽게 구현 가능하다. 상수 시간 안에 이 연산이 수행될 수 있으며 잠재 비용은 변함없다. 따라서 이것 역시 분할상환 시간을 상수로 만든다. 삽입 [ 편집 ] 삽입 연산은 하나의 구성요소를 가지고 새로운 힙을 생성한 후, 병합함으로써 수행된다. 이러한 삽입 연산에는 상수 시간이 소요되며, 잠재비용은 1만큼 증가하는데, 트리의 수가 증가되기 때문이다. 분할상환된 비용은 그러므로 여전히 상수이다. 삽입의 좀더 상세한 그림은 아래와 같다.
다른 유일한 차수를 가질 때까지 반복적으로 수행된다. 키 감소 [ 편집 ] 키 감소 연산 ( Operation decrease key ) 은 노드를 취하여 키를 감소시킨다. 이로 인해 힙의 특성이 위반되었다면 ( 새로운 키가 부모의 키보다 작다 ), 이 노드를 부모로부터 절단한다. 만일 부모가 루트가 아니면, 이 노드를 표시한다. 만일 이 노드가 이미 표시된 것이라면, 이것을 절단하고 부모를 표시한다. 이 과정을 반복하면서 위로 올라가는데, 루트 또는 표시되지 않은 노드를 만날 때까지 계속한다. 이것이 새로운 최소값이라면, 이제 최소값 포인터를 감소된 값으로 설정한다. 이 과정에서 우리는 신규 트리를 생성한다. ( 이때 이 신규 트리의 수를 k라 하자 ). 첫번째 트리를 제외한 신규 생성된
빌리자면 " 상당히 복잡한 " 그리고 " 현실적으로는 응용가능하지 않을 " 구조라고 하였다. 2012년에 만들어진 엄격한 피보나치 힙은 동일한 최악의 경우의 경계값을 가지는 보다 단순한 구조이다 ( Brodal의 것에 비하면 그렇다 ) 이 보다 엄격한 피보나치 힙이 실제로 적용했을 때 효율적인지 여부는 알려지지 않았다. 실행에서 다소 유연한 Driscoll et al. 의 힙은 merge를 제외한 나머지 연산에 대해 피보나치 힙보다 보다 나은 최악 경우의 성능을 보였다. 수행시간 [ 편집 ] 다음의 시간 복잡도는 Binary Heap, Binomial Heap, Fibonacci Heap에 대해서만 나타난 것이다. Binary heap Binomial heap Fibonacci heap MAKE
대로 수행했을 때 최악의 경우 O ( a b log n ) 만큼의 시간이 소요됨을 의미한다. 이진 힙 또는 이항 힙이라면, 이러한 순서의 연산은 O ( ( a b ) ( a b ) log n ) 의 시간이 소요될 것이다. 그러므로 비상수 요소에 의해 b가 a보다 작을 경우, 피보나치 힙은 이진 힙 또는 이항 힙보다 더 낫다. 두 피보나치 힙을 상수 분할 상환 시간 안에 병합하는 것 또한 가능하다. 이것은 이항 힙의 경우 병합 시간이 O ( log n ) 만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다. 우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에
. ( f ) 는 키 값이 23s인 노드는 현재 x가 가리키는 키값이 7인 노드에 연결되어 있고, ( g ) 에서 키값이 17인 노드는 여전히 x가 가리키는 키 값이 7인 노드에 연결되었다. ( h ) 에서 키값이 24인 노드가 키값이 7인 노드에 연결되어 있으며, A [ 3 ] 이 가리키는 노드가 없어 이 결과로 생성되는 트리의 루트를 가리키도록 설정된다. 이와 마찬가지로 ( i ) ~ ( m ) 의 과정을 수행하면 위의 그림과 같다. 이는 루트리스트의 모든 루트가 서로 다른 유일한 차수를 가질 때까지 반복적으로 수행된다. 키 감소 [ 편집 ] 키 감소 연산 ( Operation decrease key ) 은 노드를 취하여 키를 감소시킨다. 이로 인해 힙
하는데 소요되는 실제 시간은O ( k ) 이었으므로, ( 다시 한번 충분히 큰 c값을 선택하면 ) 분할상환된 실행 시간은 상수이다. 마지막으로, 삭제 연산 ( operation delete ) 은 삭제하고자 하는 구성요소의 키를 무한대로 마이너스하여 감소시킨다. 이렇게 하여 이 노드를 전체 힙에서 최소값을 보유한 노드가 되게 한다. 이제 최소값 추출 함수를 호출하여 이것을 찾아 제거한다. 이 연산의 분할상환된 실행시간은 O ( log n ) 이다. 아래의 그림으로 더 자세하게 설명하겠다 ( a ) 의 피보나치 힙에서 ( b ) 의 46을 키로가지는 노드는 키가 15로 감소했으며, 그 노드는 루트가 되고 마크가 되지 않았던 ( 24를 키로가지는 ) 부모는 마크가 되었다. ~ ( e ) 35의
피보나치 힙(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)만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다. 우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에 비해 그래프 내 두 노드 사이의 최단거리를 계산하는 데이크스트라 알고리즘 같은 중요한 알고리즘의 점근적 실행시간을 개선하는 효과를 가져온다.