피보나치 힙 (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)만큼 所要되는데 이것보다 改善된 것이고, 李瑱 힙 의 境遇는 倂合을 效率的으로 處理하지 못하는데 이에 비하면 改善된 것이다. 優先順位 큐에 對해 피보나치 힙을 使用함으로써, 다른 더 느린 優先順位 큐 資料構造를 使用하는 同一한 알고리즘에 비해 그래프 내 두 노드 사이의 最短距離를 計算하는 데이크스트라 알고리즘 같은 重要한 알고리즘의 漸近적 實行時間을 改善하는 效果를 가져온다.

救助 [ 編輯 ]

피보나치 힙은 最小-힙 特性을 만족시키는 트리들을 모아 놓은 것이다. 卽, 子息의 키는 恒常 父母의 키보다 크거나 같다. 이것은 最小 키가 恒常 트리들 中 한 트리의 루트에 있다는 것을 意味한다.

이항 힙 에 비해, 피보나치 힙의 構造는 좀더 柔軟하다. 트리는 規定된 模樣을 가지지 않는다. 極端的인 境遇, 힙의 모든 構成要素가 서로 떨어진 別個의 트리에 存在할 수도 있다. 이러한 柔軟性으로 인해, 一部 연산은 “게으른” 方式으로 遂行할 수 있다. 卽 나중 演算으로 作業을 延期(뒤로 미룸)하는 方式이다. 例를 들어, 힙의 倂合(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만큼 增加하는데, 트리의 數가 增加되기 때문이다. 分割償還된 費用은 그러므로 如前히 常數이다. 揷入의 좀더 詳細한 그림은 아래와 같다.

醫師코드는 아래와 같다.
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)이다. 글만으로 理解하기 어려울 것 같아 아래의 그림으로 詳細하게 說明하면 아래와 같다.

키 減少 [ 編輯 ]

키 減少 演算 (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)이다. 아래의 그림으로 더 仔細하게 說明하겠다

Degree 警戒의 證明 [ 編輯 ]

피보나치 힙의 分割償還된 性能은 任意의 트리 루트의 degree(子息 노드의 數), 卽O(log n)에 따라 달라지는데, 여기서n 은 힙의 크기이다.

여기서 우리는 힙 內에서 degree가 d인 任意의 노드 x를 루트로 하는 (下位)트리의 크기는 적어도F _d+2 가 되어야만 한다. 여기서F _k 은 k番째 피보나치 數이다.

Degree 境界는 이것부터 始作하여 다음의 事實, 그러니까 d≥0 人 모든 整數에 對해 ${\displaystyle F_{d+2}\geq \varphi ^{d}}$ (誘導를 통해 쉽게 證明됨)를 따른다. 여기서 φ=((1+√5))?2=1.618이다. (그리고서 우리는 ${\displaystyle 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의 높이보다 嚴格하게 더 작으므로, 우리는 이 歸納的 家庭을 ${\displaystyle {\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에 對해서만 나타난 것이다.

參考 文獻 [ 編輯 ]

• 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.