Back to : advanced-algorithms

์ฐธ๊ณ ์ž๋ฃŒ : 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$ ๋‹จ์œ„์ธ ๊ทธ๋ž˜ํ”„์—์„œ๋Š” ๋นจ๋ผ์ง€๊ธด ํ•œ๋‹ค๋Š” ๋“ฏ ํ•˜๋‹ค.