์ฐธ๊ณ ์๋ฃ : CLRS Chapter 19, MIT Lecture Note

## Motivation

Minimum Spanning Tree๋ฅผ ์ฐพ๋ Primโs algorithm์ด๋, ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋ Dijkstra Algorithm์์ ๋งค์ฐ ์ค์ํ ์ญํ ์ ํ๋ ์๋ฃ๊ตฌ์กฐ๋ก Priority queue๊ฐ ์๋ค. ๋ ์๊ณ ๋ฆฌ์ฆ์ ์คํ ๊ณผ์ ์ ๋ณด๋ฉด, ๋ค์ ๋ ์ฐ์ฐ์ด ํ์ํจ์ ์ ์ ์๋ค.

• insert(x, e) : ์๋ฃ๊ตฌ์กฐ์ ๊ฐ์  ๋๋ ์ ์ ๊ณผ ๊ทธ ๊ฐ์ค์น๋ฅผ ๋ฃ๋๋ค. ๊ฐ์ค์น๋ ๊ฐ์  ๊ฐ์ค์น๊ฑฐ๋ (Prim), ์์์ ์์ ๊ทธ ์ ์ ๊น์ง ์ค๋, ํ์ฌ๊น์ง ์ฐพ์์ง ์ต๋จ ๊ฑฐ๋ฆฌ์ด๊ฑฐ๋ (๋ค์ต์คํธ๋ผ)โฆ
• pop_min() : ์ต์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ ๊ฐ์ /์ ์ ์ ๋ฃ๋๋ค.

๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์๋ ์ฌ๋ฌ๊ฐ์ง๊ฐ ์๊ฒ ์ง๋ง, C++์ ์ผ๋ฐ์ ์ธ priority queue๋ฅผ ์ด๋ค๋ฉด ๋๋ต ์ด๋ฐ ๋๋์ผ๋ก ๊ตฌํํ  ์ ์์ ๊ฒ์ด๋ค.

bool relax(Edge edge, int u, int dist[])
{
bool flag = 0;
int v = edge.dest, w = edge.w;
if (dist[v] > dist[u] + w && (dist[u]!=INF))
{
flag = true;
dist[v] = dist[u]+w;
}
return flag;
}

void dijkstra(int dist[], int start, vector<Edge> graph[])
{
fill(dist,dist+MX,INF);
dist[start] = 0;
priority_queue<Edge> pq;
pq.push({start,0});
while(!pq.empty())
{
Edge x = pq.top();
int v = x.dest, w = x.w;
pq.pop();
if (w>dist[v])
continue;
for (auto ed : graph[v])
if (relax(ed, v, dist))
pq.push({ed.dest,dist[ed.dest]});
}
}


๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ ๋ณด๋ฉด, ๊ฐ๋์ ์ผ๋ก ์ฐ๋ฆฌ๊ฐ ์ฐพ๊ณ  ์ถ์ ๊ฒ์ ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์์ ๋ฏธ๋ฐฉ๋ฌธ ์ ์  ์ด๋ค. ์ฆ, ์ฐ๋ฆฌ๋ ์ค์ ๋ก๋ ์ ์  ์ ๋ฝ๊ณ  ์ถ์ง๋ง, priority queue์๋ ์ค์ ๋ก๋ ๊ฐ์ ์ ๋ฃ๊ณ  ์๋ค. ๋ค์ ๋งํด, ํ์ฌ ๋ฐฉ๋ฌธํ ์ ์ ์งํฉ์ด $S$ ๊ณ , ์๋ก์ด ์ ์  $x$ ๋ก ๊ฐ๊ณ  ์ถ์ ๋, ์ฐ๋ฆฌ๊ฐ ์๊ณ  ์ถ์ ๊ฒ์ $d(x, S)$ ์ง๋ง, priority queue์ ์ค์ ๋ก ๋ฃ์ ๊ฒ์ $s \in S$ ์ ๋ํด ๊ฐ๊ฐ์ $d(x, s)$ ๋ฅผ ๊ฐ๊ณ  ์๋ค. ๋ฌผ๋ก  ๊ตฌํ ์์ฒด์๋ ๋ฌธ์ ๊ฐ ์์ง๋ง, ์ด ๊ณผ์ ์์ priority queue์ ์ต๋ $E$๊ฐ์ ์ํธ๋ฆฌ๊ฐ ๋ค์ด๊ฐ๊ฒ ๋๋ฏ๋ก $E \log E$ ์๊ฐ์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.

์ $d(x, S)$ ๋ฅผ ๊ด๋ฆฌํ  ์ ์์๊น? ์ด๋, $S$ ๊ฐ ๊ณ์ ๋ฐ๋๊ธฐ ๋๋ฌธ์, $d(x, S)$ ๋ฅผ ๊ด๋ฆฌํ๋ ค๋ฉด priority_queue์ ๋ค์ ์ฐ์ฐ์ด ํ๋ ๋ ํ์ํ๊ธฐ ๋๋ฌธ์ด๋ค.

• modify(x, v) : $x$์ ๊ฐ์ค์น๋ฅผ $v$๋ก ๋ฐ๊พผ๋ค.

๊ทธ๋ฌ๋, ์ค์ ๋ก ์ ์๊ณ ๋ฆฌ์ฆ์ ์ํํ๋ ๊ณผ์ ์ ๋ณด๋ฉด, modify๋ ์ฝ๊ฐ ์ค๋ฒํฌ์ด๋ค. $S$๋ ์งํฉ์ผ๋ก์ ๋จ์กฐ์ฆ๊ฐ (์์๊ฐ ๋น ์ง์ง๋ ์๊ณ  ์ถ๊ฐ๋ง ๋๋ค) ์ด๋ฏ๋ก, $d(x, S)$ ๊ฐ ์ํ ๊ณผ์ ์์ ๋จ์กฐ๊ฐ์ํจ์ ๊ด์ฐฐํ๋ฉด, ํ์ํ ์ฐ์ฐ์ ๋ค์๊ณผ ๊ฐ์ด ์ค์ผ ์ ์๋ค.

• decrease(x, v) : $x$์ ๊ฐ์ค์น๋ฅผ $v$๋ก ์ค์ธ๋ค.

์ฌ์ ํ, C++์ priority_queue๋ heap์ผ๋ก ๊ตฌํ๋์ด ์๊ธฐ ๋๋ฌธ์ ์ ์ฐ์ฐ์ ์ง์ํ์ง ์๋๋ค. ์ ์ฐ์ฐ์ ๋น ๋ฅด๊ฒ ์ฒ๋ฆฌํ  ์ ์๋ ์๋ฃ๊ตฌ์กฐ๊ฐ ๋ฐ๋ก Fibonacci Heap์ด๋ค.

## Fibonacci Heap

ํผ๋ณด๋์น ํ์ ์ค์ ๋ก๋ ํ ์ฑ์ง์ ๋ง์กฑํ๋ ํธ๋ฆฌ ์ฌ๋ฌ ๊ฐ๋ก ๊ตฌ์ฑ๋๋ค. ์ฆ, ํธ๋ฆฌ $T_1, T_2, \dots$ ๊ฐ ํ ์ฑ์ง์ ๋ง์กฑํ๋ฉฐ, ๊ฐ ํธ๋ฆฌ์ ๋ฃจํธ ๋ธ๋๋ค์ doubly linked list๋ก ๊ด๋ฆฌํ๋ค. ์ฌ๊ธฐ์ ํ ์ฑ์ง์ด๋, ์์์ edge์์ parent node์ ๊ฐ์ค์น๊ฐ child node๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๊ฒ ํ๋ ๊ฒ์ด๋ค. ๋จ, ์ฐ๋ฆฌ๊ฐ ์๊ณ  ์๋ Binary Heap ๊ณผ๋ ๋ฌ๋ฆฌ ์์์ ํ ์ฑ์ง์ ๋ง์กฑํ๋ ํธ๋ฆฌ๋ฅผ ์ด์ฉํ  ๊ฒ์ด๋ค.

๋ช๊ฐ์ง ๋ณ์์ ์ฉ์ด๋กค ์ ์ํ๊ณ  ๊ฐ์.

• root list๋, ๋น์ฐํ, root๋ค์ ์ด์ ๋ฆฌ์คํธ๋ฅผ ๋งํ๋ค. ์ด๋ฅผ $L$ ์ด๋ผ ํ๊ณ , ๊ทธ ํฌ๊ธฐ๋ฅผ $\abs{L}$ ์ด๋ผ๊ณ  ์ฐ์.
• node x์ rank(x)๋, ๊ทธ ๋ธ๋์ ์์ ๋ธ๋์ ๊ฐ์๋ฅผ ๋งํ๋ค. ๋ํ, ํธ๋ฆฌ $T_i$์ rank๋ ํธ๋ฆฌ์ ๋ฃจํธ์ rank๋ก ์ ์ํ๋ค. ์ฆ, ๋ฃจํธ๋ก๋ถํฐ ๊ฑฐ๋ฆฌ๊ฐ 1์ธ ๋ธ๋์ ๊ฐ์.
• node x์ ์์ ๋ธ๋ $y_1, y_2, \dots y_{\text{rank}(x)}$ ๊ฐ ์๋๋ฐ, ์ด๋ค์ ์ธ๋ฑ์ค๋ ํญ์ ์ถ๊ฐ๋ ์์๋๋ก ๋งค๊ธฐ๋ฉฐ, ์ค๊ฐ์ ๋ธ๋๊ฐ ๋จ์ด์ง๋ฉด ๋๋จธ์ง์ ์ธ๋ฑ์ค๋ฅผ ์๋ฐ์ดํธํ๋ค๊ณ  ๋ณธ๋ค. linked list์์์ ์์๋ฅผ ์๊ฐํ๋ฉด ๋๋ค.
• ์ด๋ค ๋ธ๋์ ๋ํด~ ๋ผ๊ณ  ํ  ๋, ์ฐ๋ฆฌ๋ ํญ์ ๊ทธ ๋ธ๋๋ก ๋ฐ๋ก ์ฐ๊ฒฐ๋๋ ํฌ์ธํฐ๊ฐ ์๋ค๊ณ  ๊ฐ์ฃผํ๋ค. ์ด๊ฒ ์ ์ค์ํ์ง๋ ๋์ค์ ๋์ค๊ฒ ๋๋ค.
• ๊ฐ ๋ธ๋๋ง๋ค mark ๋ผ๋ boolean ๋ณ์๋ฅผ ํ๋ ๋๋ค.
• Heap ์ฑ์ง์ ๋ง์กฑํ๋ฏ๋ก, ๊ฐ ํธ๋ฆฌ์ ๋ฃจํธ๋ (๋ค๋ฅธ ํธ๋ฆฌ์ ์๊ด์์ด) ์๊ธฐ ํธ๋ฆฌ์์ ์ต์๊ฐ์ด๋ค. ์ด๋ค ์ค ๋ค์ ์ต์๊ฐ์ ํญ์ ๊ฐ์ง๊ณ  ์์ ๊ฒ์ด๋ฉฐ, ์ด๋ฅผ global-min ์ด๋ผ๊ณ  ํ์. ์ด์ , ์ฐ๋ฆฌ๊ฐ ํ์ํ ์ฐ์ฐ์ ๊ตฌํํ๊ธฐ ์ํด, ์ด ์๋ฃ๊ตฌ์กฐ์ ๋ํ ๊ธฐ๋ณธ์ฐ์ฐ๋ค์ ์ ์ํด์ผ ํ๋ค.
1. INSERT(x) : ๋ชจ๋  insert(x) ์ฐ์ฐ์, ๋ธ๋ $x$๋ฅผ ์๋ก์ด ํธ๋ฆฌ์ ๋ฃจํธ๋ผ๊ณ  ๋ณด๊ณ , ๋ธ๋ ํ๊ฐ์ง๋ฆฌ ํธ๋ฆฌ๋ฅผ root list ๋งจ ๋ค์ ์ง์ด๋ฃ๋ ๊ฒ์ผ๋ก ํ๋ค.
2. MERGE(T1, T2): Merge ์ฐ์ฐ์, ํ ์ฑ์ง์ ๋ง์กฑํ๊ธฐ ์ํด, ๋ ํธ๋ฆฌ์ ๋ฃจํธ๊ฐ ๊ฐ๊ณ  ์๋ ๊ฐ์ค์น ๊ฐ์ ํ์ธํด์, ํฐ ์ชฝ์ ์์ ์ชฝ์ ์์๋ธ๋๋ก ๋ฐ์ด๋ฃ๋๋ค.
3. CUT(x) : root์ ๋ํ cut์ ์๋ฌด๊ฒ๋ ํ์ง ์๊ณ , Root๊ฐ ์๋ ๋ธ๋๋ผ๋ฉด ๊ทธ ๋ธ๋๋ฅผ ๋ฃจํธ๋ก ํ๋ ์๋ธํธ๋ฆฌ๋ฅผ ์๋ผ์ root list ๋งจ ๋ค์ ์ง์ด๋ฃ๋๋ค. ์ด๋, ๋ค์๊ณผ ๊ฐ์ด ๊ฒฝ์ฐ๋ฅผ ๋๋๋ค.
• Parent node๊ฐ ๋งํน๋์ด ์์ง ์๋ค๋ฉด, Parent node๋ฅผ ๋งํฌํ๋ค.
• Parent node๊ฐ ์ด๋ฏธ ๋งํน๋์ด ์๋ค๋ฉด, Parent node๋ฅผ ์ฌ๊ท์ ์ผ๋ก cut ํ๋ค.

์ฆ, ์ด๋ ๋ค์ ๋งํ์๋ฉด ์ด๋ค ๋ธ๋์ ๋ํ ๋งํน์ ์์ ์ child node ์ค ์์ด๋ฒ๋ฆฐ(cut๋) ๋ธ๋๊ฐ ์๋์ง ์ฌ๋ถ ์ ๋ํ ๋งํน์ผ๋ก ์ ์ํจ์ ๋งํ๋ค. root node๋ cut๋์ง๋ ์๊ณ , mark๋์ด์ผ ํ  ์ํฉ์์๋ mark๋ฅผ ๋ฌด์ํ๊ธฐ๋ก ํ๋ค (์ด์ฐจํผ cutํ  ๋ ์๋ฌด ์ผ๋ ์์ผ๋ฏ๋ก, ์๋์ผ๋ก ์ฌ๊ท์  cut์ ์ ์ฉํ์๋ค๊ณ  ์๊ฐํด๋ ์ข๊ฒ ๋ค)

๊ฐ operation์ time complexity๋ฅผ ์๊ฐํ๋ฉด, INSERT ์ MERGE ๊ฐ $O(1)$์ ๋์ํจ์ ๋น์ฐํ๋ค. CUT์ ๊ฒฝ์ฐ, ์ฌ๊ท์ ์ผ๋ก ์ฌ๋ผ๊ฐ ์ ์์ผ๋ฏ๋ก, ์ต๋ $O(H)$, ์ฆ ํธ๋ฆฌ์ ๋์ด๋งํผ ์ฌ๊ท๋  ์ ์๋ค.

์ด ๊ธฐ๋ณธ ์ฐ์ฐ๋ค์ ์ด์ฉํด์, ๋ค์๊ณผ ๊ฐ์ด POP-MIN ๊ณผ DECREASE ๋ฅผ ๊ตฌํํ๋ค.

• DECREASE(x, v) : ๋จผ์ , $x$ ๋ฅผ CUT ํด์ ์๋ก์ด ํธ๋ฆฌ๋ก ๋ง๋  ๋ค์ decrease๋ฅผ ์ค์ ๋ก ์ํํ๋ค. root๋ฅผ decreaseํ๋ ๊ฒ์ ํ ์ฑ์ง์ด ์ ๋ ๊นจ์ง์ง ์์ผ๋ฏ๋ก ํญ์ ๊ฐ๋ฅํ๋ค. ํ์ํ๋ค๋ฉด, global-min ํฌ์ธํฐ๋ฅผ ์๋ฐ์ดํธํ๋ค. (decrease ๊ฒฐ๊ณผ ํ์ฌ์ global-min๋ณด๋ค ์์์ก๋ค๋ฉด).
• POP-MIN() : ์ฐ๋ฆฌ๋ global-min ์ ํฌ์ธํฐ๋ฅผ ๊ฐ์ง๊ณ  ์์ผ๋ฏ๋ก, popํด์ผ ํ  ๋ธ๋๋ฅผ $O(1)$์ ์ ์ ์๋ค. ์ด ๋ธ๋๋ฅผ ์ญ์ ํ๋ฉด์, ์ด ๋ธ๋ ์๋์ ๋ฌ๋ ค์๋ ๋ธ๋๋ค์ ๋ชจ๋ root list์ ๋ผ์๋ฃ๋๋ค. ์ฆ, root list๋ ์ต๋ # of children of global-min - 1 ๋งํผ ์ฆ๊ฐํ๊ฒ ๋๋ค. ์ด๋, ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ์ํํ๋ค.
• ์ด๋ ๊ฒ ๋์ด๋ root list๋ฅผ ๋ค์ ์ค์ผ ๊ฒ์ด๋ค. rank๊ฐ ๊ฐ์ ๋ tree๋ฅผ merge ํด์, rank๊ฐ ํ๋ ํฐ ํธ๋ฆฌ๋ฅผ ์ป๋๋ค. ์ด๋ฅผ rank๊ฐ ์์ ์ชฝ๋ถํฐ ๋ฐ๋ณต์ ์ผ๋ก ์ํํด์, rank๊ฐ $k$ ์ธ ํธ๋ฆฌ๊ฐ ๋ชจ๋ ์ต๋ ํ๋์ฉ๋ง ์๊ฒ ํ๋ค. ๋ง์ฝ ์ฒ์์ ๋ญํฌ๊ฐ 1์ธ ํธ๋ฆฌ๊ฐ 4๊ฐ, 2์ธ ํธ๋ฆฌ๊ฐ 3๊ฐ, 3์ธ ํธ๋ฆฌ๊ฐ 1๊ฐ ์๋ค๋ฉด, 1์ธ ํธ๋ฆฌ๋ค์ ํฉ์ณ์ rank = 2 ์ธ ํธ๋ฆฌ๋ฅผ 2๊ฐ ์ป๊ณ , ์ด๋ ๊ฒ ์ด 5๊ฐ์ rank-2 ํธ๋ฆฌ๋ฅผ ํฉ์ณ์ rank-2 ํธ๋ฆฌ 1๊ฐ์ rank-3 ํธ๋ฆฌ 2๊ฐ๋ฅผ ์ถ๊ฐํ๋ ค (0, 1, 3, 0), ๋ง์ง๋ง์ผ๋ก ์ด๋ค์ ํฉ์ณ rank-4 ํธ๋ฆฌ๋ฅผ ํ๋ ์ป์ด (0, 1, 1, 1)๋ก ๋ง๋๋ ์์ด๋ค.
• ์ต์ข์ ์ผ๋ก ํฉ์ณ์ง root list๋ฅผ ๋๋ฉด์, global-min์ ๋ค์ ์ง์  ์ฐพ๋๋ค.

์ฐ๋ฆฌ์ ๋ง์ง๋ง ๋ชฉํ๋, ์ด ์ฐ์ฐ๋ค์ complexity๊ฐ insert, decrease, pop-min ๊ฐ๊ฐ์ด Amortized $O(1)$, $O(\log n)$, $O(1)$ ์์ ๋ณด์ด๋ ๊ฒ์ด๋ค.

## Time complexity์ ์ฆ๋ช

๋จผ์ , ๋ค์์ ๋งค์ฐ ์ค์ํ Lemma ๋ฅผ ๋ณด์. ์ด Lemman๋ ์ด ์๋ฃ๊ตฌ์กฐ์ ์ด๋ฆ์ด ํผ๋ณด๋์น ํ ์ธ ์ด์ ์ด๋ค.

### Maximum Rank Lemma

ํผ๋ณด๋์น ํ์ ์ํ ๊ณผ์ ์์ ์๊ธธ ์ ์๋ ํธ๋ฆฌ๋ค์ ๋ํ์ฌ, maximum rank of tree with n nodes $= O(\log n)$

ํผ๋ณด๋์น ํ์ ์ํ ๊ณผ์ ์ ๋ณด๋ฉด, merge๋ ๋ฐ๋์ ๋ญํฌ๊ฐ ๊ฐ์ ํธ๋ฆฌ์์๋ง ์ผ์ด๋จ์ ๊ด์ฐฐํ  ์ ์๋ค. ์ด๋ฅผ Merge Rule ์ด๋ผ๊ณ  ๋ถ๋ฅด์.

์ด๋ฅผ ๋ณด์ด๋ ๊ฒ์, ๋๋ต ๋ค์๊ณผ ๊ฐ๋ค. ๋จผ์ , $x$ ์ ์์๋ธ๋ ์ค $i$ ๋ฒ์งธ ๋ธ๋๋ฅผ ์๊ฐํด ๋ณด์. ์ด ๋ธ๋๋ ์ ์ด๋ $i$๋ฒ์งธ์ ๋ฌ๋ฆฐ ๋ธ๋์ด๋ฏ๋ก, ์ด ๋ธ๋๊ฐ ๋ฌ๋ ค ์๋ค๋ ๊ฒ์ ์ ์ด๋ ์์ $i-1$๊ฐ์ ๋ธ๋๊ฐ ๋ฌ๋ฆฐ ์ํ์๋ค๋ ๋ป์ด๋ค. ๊ทธ๋ฌ๋ฏ๋ก $x$์ $i$๋ฒ์งธ ์์ $y_i$ ๊ฐ ๋ฌ๋ฆฌ๊ธฐ ์ ์, $y_i$์ rank๋ $i-1$ ์ด์์ ๊ฒ์ด๋ค.

์ฌ๊ธฐ์, $y_i$ ๋ ์ต๋ 1๊ฐ์ ์์ ๋ธ๋๋ฅผ cut์ผ๋ก ์์ด๋ฒ๋ฆด ์ ์๋ค. ๊ทธ ์ด์ ์์ด๋ฒ๋ฆฐ๋ค๋ฉด mark์ ์์น์ ์ํด, $y_i$ ๊ฐ $x$๋ก๋ถํฐ ๋จ์ด์ ธ ๋๊ฐ์ ๊ฒ์ด๋ค. ๋ฐ๋ผ์, $x$์ $i$ ๋ฒ์งธ ์์์ ์ ์ด๋ $i-2$ ์ ๋ญํฌ๋ฅผ ๊ฐ๋๋ค.

์ด ์์น์ ์ฌ๊ท์ ์ผ๋ก ์ ์ฉํ๋ฉด, rank๊ฐ $k$ ์ธ ๊ฐ์ฅ ์์ ํธ๋ฆฌ์ ํฌ๊ธฐ๋ฅผ $P_k$ ๋ผ๊ณ  ํ  ๋, ๋ค์์ ์ฌ๊ท์์ ์ป๋๋ค. $$P_k \geq 1 + \sum_{i = 0}^{k-2} P_{i}$$

$k$ ๋ฒ์งธ ํผ๋ณด๋์น ์ $F_k$ ์ ๋ํด, ๋ค์๊ณผ ๊ฐ์ ์ฌ์ค์ด ์ ์๋ ค์ ธ ์๋ค. $$F_k = 1 + \sum_{i = 0}^{k-2} F_{i}$$

๋ค๋ง, $P_0 = 1$, $P_1 = 2$ ๋ฅผ ์ด์ฉํ์ฌ ์ธ๋ฑ์ค๋ฅผ ์ ๋ง์ถ์ด ์ฃผ์ด์ผ ํ๋ค. ์ธ๋ฑ์ค๋ฅผ ์ ๋ง์ถ์ด ์ฃผ๋ฉด, $P_k$ ๊ฐ ์ ์ด๋ ํผ๋ณด๋์น ์์ด๋งํผ ๋น ๋ฅด๊ฒ ์ฆ๊ฐํจ์ ์๋ค. ๊ทธ๋ฆฌ๊ณ  ํผ๋ณด๋์น ์๊ฐ $(1.5)^k$ ๋ณด๋ค ๋น ๋ฅด๊ฒ ์ฆ๊ฐํจ์ด ์ ์๋ ค์ ธ ์์ผ๋ฏ๋ก, $P_k$ ๋ ์ง์์ ์ผ๋ก ๋น ๋ฅด๊ฒ ์ฆ๊ฐํ๋ค. ๋ฐ๋๋ก ๋งํ๋ฉด, ๋ธ๋๊ฐ $n$ ๊ฐ์ธ ํธ๋ฆฌ์ ์ต๋ rank๋ $O(\log n)$ ์์ด ์ฆ๋ช๋์๋ค.

### Amortized Analysis

Amortized analysis ์ค potential method๋ฅผ ์ฌ์ฉํ์. potential function $\phi$ ๋ฅผ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค.

$\phi(DS) = \text{size of root-list} + 2 * \text{number of marked nodes}$

$\phi(DS_0)$์ ๋น ํผ๋ณด๋์น ํ์ผ๋ก ์๊ฐํ๋ฉด $phi(DS_i) \geq \phi(DS_0)$ ์์ด ์๋ชํ๋ฏ๋ก ์ ํจ์๋ potential function์ผ๋ก validํ๋ค. $C_{\text{amortized}} = C_{\text{real}} + \Delta\phi$ ๋ฅผ ์ด์ฉํด์ ๋ถ์ํด๋ณด๋ฉด,

• INSERT : ์ค์  cost ๋ $O(1)$ ์ด๊ณ , $\Delta\phi$ ๋ root๋ง ํ๋ ๋์ด๋๋ฏ๋ก 1์์ ์ ์ ์๋ค.

• POP-MIN : ์ค์  cost ๋ฅผ ๋จผ์  ์๊ฐํ๋ฉด, $O(1)$ ๋ง์ ๋ธ๋๋ฅผ ์ง์ฐ๊ณ , ๊ทธ ๋ธ๋์ children์ ์๋งํผ, ์ฆ rank(global-min) ๋งํผ root list๋ฅผ ๋๋ ค์ผ ํ๋ค. ์ด ๊ฐ์ $r$ ์ด๋ผ ํ์. ๋ง์ง๋ง์ผ๋ก, ๋ชจ๋  ํธ๋ฆฌ๋ค์ ๋๋ฉด์ merge ํ  ์ ์๋์ง ์ฌ๋ถ๋ฅผ ํ์ธํด์ผ ํ๋๋ฐ, ์ด๋ rank์ ๋ฐ๋ผ ๋ฒํท์ ๋ง๋ ๋ค๊ณ  ์๊ฐํ๋ฉด $O(\abs{L} + \text{maximum rank})$ ์๊ฐ์ ๊ฐ๋ฅํ๋ค. $\Delta \phi$ ๋ฅผ ๋ชํํ ์ก๊ธฐ ์ด๋ ค์ด๋ฐ, ์ด๋ ๊ฒ ์๊ฐํด ๋ณด์. ์ผ๋จ root-list ์ ํฌ๊ธฐ๊ฐ ์๋ ์ผ๋ง์๋์ง๋ ์ ์ ์์ผ๋, maximum rank ๊ฐ๋ณด๋ค ์ปค์ง ์๋ ์๋ค. (MERGE ๊ณผ์ ์ ๊ฑฐ์น๋ฏ๋ก) ๋ํ, marked node์ ๊ฐ์๋ ์๋ marked์๋์ง ์ ์ ์๋ ๋ธ๋๋ค์ด root๊ฐ ๋๋ฉด์ ๊ฐ์ ๋ก unmark ๋๋ ๊ณผ์ ์ ๊ฑฐ์น๋ฏ๋ก, ๋ฐ๋์ ์ค์ด๋ ๋ค. ๋ฐ๋ผ์, $\Delta \phi \leq$ maximum rank ์ ๋๋ ์ ์ ์๋ค. $\abs{L}$, ์ต๋ ๋ญํฌ ๋ ๋ชจ๋ $O(\log n)$ ์ด๋ฏ๋ก POP์ฐ์ฐ์ amortizeํด๋ $O(\log n)$ ์ ์ด๋ฃจ์ด์ง๋ค.

• DECREASE : Decrease๋ฅผ ์ด๋ ต๊ฒ ๋ง๋๋ ๊ฐ์ฅ ํฐ ์์ธ์ cut์ด ๋ช๋ฒ ์ผ์ด๋ ์ง ์ ์ ์๋ค๋ ์ ์ด๋ค. ์ต์์ ๊ฒฝ์ฐ, cut์ height of tree ๋งํผ ์ผ์ด๋๋๋ฐ, ์ด ๊ฐ์ $h$ ๋ผ ํ์. ์ด๋, potential function์ ๋ณํ๋ $\Delta \phi$ ๋ฅผ ์๊ฐํด ๋ณด๋ฉด, ํ๋ฒ cut์ด ์ผ์ด๋  ๋๋ง๋ค marked node๊ฐ ํ๋์ฉ ์ค์ด๋ค๊ณ , root-list์ ํฌ๊ธฐ๊ฐ ํ๋์ฉ ๋์ด๋๋ค. ์์๋ฅผ ๊ณ์ฐํด ๋ณด๋ฉด $\Delta \Phi$ ๊ฐ $-h$ ์์ ์ ์ ์๋ค. cut์ ํ๋ ์๊ฐ ์ธ์, ๋๋จธ์ง ์ฐ์ฐ๋ค์ ์์ ์๊ฐ์ ๋ฒ์ด์ง๋ฏ๋ก, potential drop ์ actual cost์ ํฉ์ณ ๋ณด๋ฉด amortized $O(1)$ ์์ ์๋ค.

## Why thenโฆ

์ฐ๋ฆฌ๋ ์ด๋ ๊ฒ decrease-key๋ผ๋ ์ฐ์ฐ์ $O(1)$ ์ ์ํํ๋ ๋๋ผ์ด ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ป์๋ค. ์ด์  dijkstra ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ  ๋ priority queue์ vertex๋ฅผ ์ง์  ๋๋ ค๋ฃ๊ณ  decrease๋ฅผ ํ๋ ์์ผ๋ก ๊ตฌํํ๋ฉด $O(V \log V)$ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ป๋๋ค.

๊ฐ์ธ์ ์ผ๋ก ๋๋ ํ๋ฒ๋ ์ด๋ ๊ฒ ๊ตฌํํ ์ฝ๋๋ฅผ ๋ณธ ์ ์ด ์๊ณ  ์๋ง ์ฝ๋ ์ฌ๋๋ ๋ง์ฐฌ๊ฐ์ง์ผํ๋ฐ, ๊ทธ ์ด์ ๋ ํฌ๊ฒ ๋ ๊ฐ์ง๋ก ๋ค ์ ์๋ค.

• ๊ตฌํ์ด ์๋นํ ์ด๋ ต๋ค. DECREASE, POP ๋ชจ๋ ํฌ์ธํฐ์ ๋งํฌ๋ ๋ฆฌ์คํธ๋ฅผ ๋งค์ฐ ์กฐ์ฌ์ค๋ฝ๊ฒ ์ ์ด์ฉํด์ผ ํ๋ค.
• ์ค์ ๋ก ์์ฑํด๋ณด๋ฉด ๋งค์ฐ ๋๋ฆฐ๋ฐ, binary heap์ด ๊ทธ๋ฅ ๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ฅผ ์ ์ฃผ๋ ์์ผ๋ก ์ ๋ง ๋น ๋ฅด๊ฒ ๊ตฌํํ  ์ ์๋ ๋ฐ๋ฉด Fibonacci heap์ ํ์ฐ์ ์ผ๋ก ํฌ์ธํฐ๋ฅผ ์ด์ฉํ ๋งํฌ๋ ๋ฆฌ์คํธ ๊ตฌ์กฐ๋ก ๋ง๋ค์ด์ผ ํ๊ณ , ๋จ์ ์ ๊ทผ์ ๋นํด ์ด๋ฐ ์์ผ๋ก ๊ตฌํํ๋ฉด ๋ช ๋ฐฐ์ ์์๊ฐ ๋ถ๋๋ค.

๋ง์ฝ $E$๊ฐ $V$์ ๋นํด ์๋นํ ํฐ dense graph ๋ผ๋ฉด, priority queue๋ฅผ ์คํผ๋์ํ๋ ๋ฐฉ๋ฒ์ด ๋  ์ ์๊ฒ ์ง๋ง, $E$ ๊ฐ $O(V)$ ๋ด์ง๋ ๊ทธ ์ธ์ ๋ฆฌ์ธ ์์์์๋ ๋ณ๋ก ๋์์ด ๋์ง ์๋๋ค. ์ฌ๊ธฐ์ ๊ธฐ ์ฐพ์๋ณด๋ $V$๊ฐ 10๋ง ๋จ์, $E$๊ฐ $10^7$ ๋จ์์ธ ๊ทธ๋ํ์์๋ ๋นจ๋ผ์ง๊ธด ํ๋ค๋ ๋ฏ ํ๋ค.