개발을 하면서 한 번쯤은 들어봤을 자료구조인 피보나치 힙이다. 알고리즘 등에서 주로 언급되는데 타이머 관리나 네트워크 플로우 등에 이론적으로 적합하다는 이야기를 심심치 않게 듣는다(실무적로는 그렇지 않다는 뜻).
· 피보나치 힙(Fibonacci heap)이란
먼저 개념을 짚고 넘어가자면 피보나치 힙은 여러 개의 힙을 묶어 관리하는데, 각 노드가 관리하는 자식 수에 대한 제약을 추가함으로써 피보나치 수열과 연관된 규칙이 생기고 성능적 이점을 취하는 자료 구조이다. 삽입, 값 감소, 최소 값 조회 및 제거 동작이 핵심이다.
빠른 결론이 필요한 사람들을 위해 결론부터 말하자면 앞서 말했던 것처럼 이 자료구조는 이론적으로 성능이 좋지만 실무에선 다음의 단점들이 훨씬 부각되어 잘 사용되지 않는다.
- 자료구조의 동작은 비용을 많이 쓰지 않지만 포인터 기반으로 트리를 구성하기 때문에 메모리 친화성을 해쳐 공간 지역성(Spatial locality)이 중요한 CPU 캐시 미스가 빈번해진다.
- 자료구조 특성 상 조건 검사를 많이 수행해야 하여 Branch가 무거워지는 문제와 함께 구현 복잡도가 높은 편이다.
- 평균적인 성능은 높게 평가되지만 최소 값 제거(Extract-Min)에서 순간적으로 폭발적인 비용을 발생시키기도 해 안정적인 시스템 동작에 악영향을 준다.
· 피보나치 힙의 동작
이 자료구조가 무엇인진 앞서 알아보았으니 중요한 동작에 대해 알아보자. 피보나치 힙에 대한 삽입과 최소 값 조회는 O(1) 시간으로 수행되고, 동작도 복잡하지 않다. 중요한 것은 최소 값 제거와 값 감소이다.
이 동작들에서 핵심적인 키워드는 Heap, Degree, Mark/Cascading-cut 이다. 각각은 아래에서 설명하겠다.
- 피보나치 힙
피보나치 힙은 RootList라는 컬렉션을 관리하고, 이곳에 최소 힙 조건(부모 노드가 자식보다 작은 값을 가지는 형태)을 만족하는 트리의 Root node들을 연결해놓는다. 각 노드는 Degree라는 정보를 추가로 가지고 있는데, 자식의 수를 의미한다. Degree를 잘 기억해놓자.
피보나치 힙이 관리하는 트리에 Max-heap을 사용하는 것도 불가능하진 않지만 일반적이지 않다.
- 삽입 (Insert)
RootNode에 새로운 노드를 추가한다. 이땐 단일로 존재하는 노드이며, 이때 추가되는 노드의 Degree는 0이다. 인덱스도 중요하지 않고 단순 추가이므로 O(1) 시간에 수행된다.
- 최소 값 조회 (Find-Min)
피보나치 힙이 관리하는 Min 포인터를 통해 즉시 최소 값을 찾는다. 따라서 O(1) 시간에 수행된다.
이 Min 포인터는 노드 상태가 변경될 때 업데이트 되는데, 최악의 경우가 최소 값 제거 이후 RootList를 순회하여 최소 값을 찾는 것이라 큰 비용으로 치지 않는다.
- 최소 값 제거 (Extract-Min)
최소 값을 제거하기 전에 전체 RootList에 대한 정렬이 발생한다. 이 정렬은 RootList 중 같은 Degree를 가지고 있는 두 트리를 병합(Consolidation)하는 과정을 반복하는데, 이것으로 RootList 크기를 관리한다.
같은 Degree의 두 트리 루트 중 더 큰 값을 가지는 루트를 작은 값의 루트 자식으로 만든다. 포인터 연결이므로 자연스럽게 자손들의 루트도 변경된다. 이 동작은 사실상(Amortized) O(logN) 시간에 수행된다.
피보나치 힙의 정렬은 Extract-Min에서만 발생한다.
앞선 설명만으론 Extract-Min의 수행 시간이 O(logN)이 아니라 O(N)에 버금가는 수행 시간을 가질 것으로 예상된다. 이것은 Decrease-Key의 Mark/Cascading-cut 동작을 통해 평균적으로 O(logN)의 수행 시간을 보장 받는다.
- 값 감소 (Decrease-Key)
피보나치 힙에서 특정 노드의 값을 감소시킬 수 있다. 기본적으로 Min-heap을 따르는 피보나치 힙에서 노드의 값을 감소시키면 자식의 값이 부모의 값보다 작아지는 경우가 생긴다. 이 경우 Min-heap 룰을 위배하는 것이기 때문에 구조 변경이 불가피하다. 자식의 값이 부모의 값보다 작아지지 않았다면 아무런 일도 일어나지 않는다.
값 감소로 부모보다 값이 작아진 자식은 부모에서부터 떨어져 나와 RootList에 독립한다. 이것은 Cut이라 하고, Cut이 발생한 부모는 Mark 상태에 변동이 생긴다.
Mark State
해당 노드에서 자식 값 감소로 인해 자식 손실(Cut)이 발생할 경우 이것을 기록해놓는 상태값이다.
- 첫 번째 자식 손실: Mark
- Mark 상태에서 다시 자식 손실 발생: 부모도 Cut되어 RootList로 이동 (Cascading-cut)
자식이 Cut되면 부모는 다음 규칙을 따른다.
앞선 Extract-Min의 병합 규칙과 Mark/Cutcascading-cut 덕분에 피보나치 힙의 각 노드들은 Degree에 대해 피보나치 수열에 비례하는 크기의 서브 트리를 가지게 된다. 따라서 Degree에 O(logN)이라는 상한이 생기고 Extract-Min에서 병합의 평균 수행 시간을 O(logN)으로 보장할 수 있다.
Mark/Cascading-cut이 없으면 반복적인 Decrease-Key에서 큰 트리 구조를 유지할 수 없다. Root의 자식 노드들이 반복적인 자식 손실을 겪으면 최악의 경우 트리의 노드 수가 (Root의 Degree - 1)이 된다.
이러한 트리의 Root가 Extract 될 경우 자식들이 RootList에 펼쳐지면서 정렬 동작이 O(N)에 수렴하게 된다.
Increase 시에는 힙 조건 위반이 부모가 아닌 자식과 이루어진다. 이 경우 추가적인 구현이 필요한데, 구현 및 동작의 비용이 커서 요소 삭제 후 다시 삽입하는 게 낫다.
이러한 동작들이 적절히 잘 사용되면 뛰어난 효과를 보이는 자료구조이겠지만, 앞서 말했던 것처럼 해당 자료구조를 유지하기 위해 필요한 포인터 관리나 구현 난이도 등이 실무 단계에서 단점으로 작용한다.
피보나치 힙에서 가장 구현이 어려운 것은 Mark/Cascading-cut인데, 이 핵심 기능을 사용하는 Decrease-Key 즉, 우선순위 재조정 동작이 생각보다 흔치 않다는 것이다. 앞서 언급한 Increase처럼 Decrease도 해당 요소를 제거하고 다시 추가하는 게 일반적이기도 하다. 따라서 이론적인 내용으로만 알고 실제로는 다른 자료구조들을 차용하는 것이 대부분 낫다.
