피보나치 힙 - 위키백과, 우리 모두의 백과사전 피보나치 힙 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 피보나치 힙 ( Fibonacci heap ) 자료구조는 두 가지 목적으로 사용된다. 첫째는 " 병합 가능한 힙 " 의 몇가지 연산 지원이며, 둘째는 분할 상환을 빈번히 수행하는 응용 프로그램에 매우 적합하도록 상수의 분할 상환 시간을 가지는 것이다. 컴퓨터 과학 ( computer science ) 에서 피보나치 힙 ( Fibonacci heap ) 은 우선순위 큐 ( priority queue ) 연산을 위한 자료 구조로, 힙 - 정렬된 트리를 모아놓은 자료 구조이다. 이진 힙 ( binary heap ) 및 이항 힙 ( binomial heap ) 등 다른 많은 우선순위 큐 자료구조에 비해 더 나은 분할 상환된 실행 시간 ( amortized running time ) 을 보인다. 피보나치 힙은 Michael L. Fredman과 Robert E. Tarjan이 1984년 개발하였고, 1987년 과학 저널에 발표하였다. 이들은 실행 시간 분석에 피보나치 수가 사용된 것을 따라 피보나치 힙이라 명명하였다. 피보나치 힙에서, 최솟값 탐색 ( find
으로 인해, 일부 연산은 " 게으른 " 방식으로 수행할 수 있다. 즉 나중 연산으로 작업을 연기 ( 뒤로 미룸 ) 하는 방식이다. 예를 들어, 힙의 병합 ( merge ) 은 두개의 리스트로 구성된 트리를 단순히 결합함으로써 가능하다. 그리고 키 감소 연산 ( decrease key operation ) 은 이 노드의 부모로부터 노드를 절단한 후, 새로운 트리를 형성하는 식으로 수행한다. 그러나, 요구되는 실행시간을 달성하기 위해 어느 시점에 어떤 순서가 힙에 도입될 필요가 있다. 특히, 노드의 degree ( 여기서 degree란 자식의 수를 의미한다 ) 가 상당히 낮게 유지된다. 즉 모든 노드는 degree가 많아야O ( log n ) 이 되며, degree가 k인 노드를 루트로 하는 하위트리의 크기는 적어도Fk2이다. 여기서Fk 은 k번째 피보나치 수이다. 이것은 루트가 아닌 노드 ( non - root node ) 에서는 최대 하나의 자식을 절단할 수 있다는 규칙에 의해 달성된다. 두번째 자식이 절단될 때, 이 노드 자체는 이것의 부모로부터 절단될 필요가 있으며, 이것이 새로운 트리의 루트가 된다. ( 아래의 Pro
저널에 발표하였다. 이들은 실행 시간 분석에 피보나치 수가 사용된 것을 따라 피보나치 힙이라 명명하였다. 피보나치 힙에서, 최솟값 탐색 ( 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보다 작을 경우, 피보나치 힙은 이진 힙 또는 이항 힙보다 더 낫다. 두 피보나치 힙을 상수 분할
5개의 순서를 갖는 최소힙 트리와 14개의 노드로 이루어져 있으며, 점섬은 루트 리스트를 나타낸다. 힙의 최소 노드는 키값 3을 가지고 있으며, 검은색 노드는 마크 ( mark ) 되어 있다. 이런 피보나치 힙의 잠재비용은 52 * 3 = 11이다. ( b ) 포인터 p ( 위쪽 방향 화살표 ), child ( 아래쪽 방향 화살표 ), left와 rifght ( 왼쪽, 오른쪽 방향 화살표 ) 를 보여주는 좀더 완전한 표현이라 할 수 있다. 피보나치 힙은 최소 - 힙 특성을 만족시키는 트리들을 모아 놓은 것이다. 즉, 자식의 키는 항상 부모의 키보다 크거나 같다. 이것은 최소 키가 항상 트리들 중 한 트리의 루트에 있다는 것을 의미한다. 이항 힙에 비해, 피보나치 힙의 구조는 좀더 유연하다. 트리는 규정된 모양을 가지지 않는다. 극단적인 경우, 힙의 모든 구성요소가 서로 떨어진 별개의 트리에 존재할 수도 있다. 이러한 유연성으로 인해, 일부 연산은 " 게으른 " 방식으로 수행할 수 있다. 즉 나중 연산으로 작업을 연기 ( 뒤로 미룸 ) 하는 방식이다. 예를 들어, 힙의 병합 ( merge ) 은 두개의 리스트
년에 만들어진 엄격한 피보나치 힙은 동일한 최악의 경우의 경계값을 가지는 보다 단순한 구조이다 ( Brodal의 것에 비하면 그렇다 ) 이 보다 엄격한 피보나치 힙이 실제로 적용했을 때 효율적인지 여부는 알려지지 않았다. 실행에서 다소 유연한 Driscoll et al. 의 힙은 merge를 제외한 나머지 연산에 대해 피보나치 힙보다 보다 나은 최악 경우의 성능을 보였다. 수행시간 [ 편집 ] 다음의 시간 복잡도는 Binary Heap, Binomial Heap, Fibonacci Heap에 대해서만 나타난 것이다. Binary heap Binomial heap Fibonacci heap MAKE - HEAP [UNK] ( 1 ) [UNK] ( 1 ) [UNK] ( 1 ) INSERT [UNK] ( lg n ) O ( lg n ) [UNK] ( 1 ) MINIMUM [UNK] ( 1 ) O ( lg n ) [UNK] ( 1 ) EXTRACT - MIN [UNK] ( lg n ) [UNK] ( lg n ) O ( lg n ) UNION [UNK] ( n ) O ( lg n ) [UNK] ( 1 ) DECREASE - KEY [UNK] ( lg n ) [UNK] ( lg n ) [UNK] ( 1 ) DELETE [UNK] ( l
, Pairing Heap, Brodal Heap, Rank Pairing Heap 등을 일컫는다. 빈 자료구조에서부터 시작해서 몇 개의 연산을 순차적으로 수행하는데 걸리는 전체 실행시간은 위에서 계산하였던 경계값 내에서 그 범위가 정해지기는 하지만, 이 순차 수행하는 연산 중 일부 연산 ( 매우 적기는 하지만 ) 은 완료하는데 매우 오랜 시간이 소요될 수 있다 ( 특히, 삭제연산 및 최소값 삭제연산은 최악의 경우 실행하는데 선형 시간 ( linear time ) ( linear time ) 이 소요된다 ). 이러한 이유로 피보나치 힙과 다른 분할상환된 자료 구조는 실시간 시스템에는 적합하지 않을 수 있다. 최악의 경우의 성능이, 피보나치가 가지는 분할상환 성능과 동일한 자료 구조를 새로 만드는 것이 가능하다. 그러한 구조 중 하나가 Brodal queue인데, 이것을 창안한 창안자의 말을 빌리자면 " 상당히 복잡한 " 그리고 " 현실적으로는 응용가능하지 않을 " 구조라고 하였다. 2012년에 만들어진 엄격한 피보나치 힙은 동일한 최악의 경우의 경계값을 가지는 보다 단순한 구조이다 ( Brodal의 것에 비하면 그렇다 ) 이 보다 엄격한 피보나치 힙이 실제로
n ) 의 시간이 소요될 것이다. 그러므로 비상수 요소에 의해 b가 a보다 작을 경우, 피보나치 힙은 이진 힙 또는 이항 힙보다 더 낫다. 두 피보나치 힙을 상수 분할 상환 시간 안에 병합하는 것 또한 가능하다. 이것은 이항 힙의 경우 병합 시간이 O ( log n ) 만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다. 우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에 비해 그래프 내 두 노드 사이의 최단거리를 계산하는 데이크스트라 알고리즘 같은 중요한 알고리즘의 점근적 실행시간을 개선하는 효과를 가져온다. 목차 1 구조 2 연산의 구현 3 최소값 찾기 4 삽입 5 최소값 추출 6 키 감소 7 Degree 경계의 증명 8 최악의 경우 9 수행시간 10 참고문헌 구조 [ 편집 ] 위의 그림에서, ( a ) 에 해당하는 것은 피보나치 힙은 5개의 순서를 갖는 최소힙 트리와 14개의 노드로 이루어져 있으며, 점섬은 루트 리스트를 나타낸다. 힙의 최소 노드는 키값 3을 가지고 있으며, 검은색 노드는 마크 ( mark
가 되고 마크가 되지 않았던 ( 24를 키로가지는 ) 부모는 마크가 되었다. ~ ( e ) 35의 키를 가지는 노드는 키가 5로 감소했다. 에서 그 노드는 5를 키로 가지는 루트가 되었다. 26을 키로 가지는 부모는 마크되어 있어 연속적인 분리가 발생한다. 26을 키로 가지는 노드는 부모로부터 분리되고 마크가 안된 루트가 ( d ) 에서 된다. 또 24를 키로 가지는 노드가 마크되어 있으므로, 다시 연속적인 분리가 발생한다. 이 노드는 그의 부모로부터 분리되고 마크가 안된 루트가 ( e ) 에서 된다. 7을 키로 갖는 노드가 루트므로 연속적인 분리는 여기서 멈추게 된다. Degree 경계의 증명 [ 편집 ] 피보나치 힙의 분할상환된 성능은 임의의 트리 루트의 degree ( 자식 노드의 수 ), 즉O ( log n ) 에 따라 달라지는데, 여기서n 은 힙의 크기이다. 여기서 우리는 힙 내에서 degree가 d인 임의의 노드 x를 루트로 하는 ( 하위 ) 트리의 크기는 적어도Fd2가 되어야만 한다. 여기서Fk 은 k번째 피보나치 수이다. Degree 경계는 이것부터 시작하여 다음의 사실
sum - { i = 2 } ^ { d } F - { i } = 1 [UNK] 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 등을 일컫는다. 빈 자료구조에서부터 시작해서 몇 개의 연산을 순차적으로 수행하는데 걸리는 전체 실행시간은 위에서 계산
. 최소 추출 연산의 전체적인 분할상환 실행시간은 그러므로 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 ) 의 과정을 수행하면 위의 그림과 같다. 이는 루트리스트의 모든 루트가 서로 다른 유일한 차수를 가질 때까지 반복적으로 수행된다. 키 감소 [
피보나치 힙(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)만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다. 우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에 비해 그래프 내 두 노드 사이의 최단거리를 계산하는 데이크스트라 알고리즘 같은 중요한 알고리즘의 점근적 실행시간을 개선하는 효과를 가져온다.