피보나치 힙

피보나치 힙은 가장 작은 값을 먼저 꺼내 주는 힙의 하나입니다. 값을 넣거나 이미 넣은 값을 줄이는 일을 거의 공짜로 해 줍니다. 대신 정리할 일을 미뤄 두었다가 가장 작은 값을 꺼낼 때 한꺼번에 합니다. 최단 경로 찾기처럼 값 줄이기를 아주 많이 부르는 계산을 빠르게 하려고 만든 구조입니다.

쉽고 빠른 이해

피보나치 힙은 가장 급한 것부터 꺼내 주는 우선순위 큐를 만드는 방법 하나입니다. 서류를 받는 대로 책상에 쌓아 두는 사람과 같습니다. 이 사람은 가장 급한 서류를 찾아야 할 때만 더미를 정리합니다.

흔히 쓰는 이진 힙은 넣을 때마다, 순위를 앞당길 때마다 조금씩 정리합니다. 길 찾기 계산처럼 순위 앞당기기(키 줄이기)를 수없이 부르는 곳에서는 이 정리가 쌓여 느려집니다.

어떻게 도나:

1. 넣을 때는 노드 하나짜리 트리를 목록에 붙이고 끝냅니다
2. 가장 작은 값을 꺼낼 때 밀린 트리들 가운데 자식 수가 같은 트리끼리 합칩니다
3. 값을 줄여 순서가 깨지면 그 부분을 잘라 목록에 올립니다

대가는 꺼내기 한 번이 오래 걸릴 수 있다는 점입니다. 노드마다 포인터가 많아 메모리를 많이 씁니다. 흔한 크기의 입력에서는 이진 힙보다 느린 경우가 많습니다.

상세

이 절은 피보나치 힙이 무엇을 빠르게 하려고 나왔는지부터 봅니다. 견주는 기준은 가장 흔한 힙인 이진 힙입니다.

그다음 값 다섯 개와 트리 몇 그루로 넣기·꺼내기·키 줄이기를 차례로 따라갑니다. 끝으로 이름에 피보나치가 붙은 까닭과, 실무 코드에서 드문 까닭을 봅니다.

우선순위 큐와 키 줄이기

우선순위 큐는 넣은 항목 가운데 가장 급한 것부터 꺼내 주는 자료구조입니다. 항목마다 급한 정도를 나타내는 값을 붙입니다. 이 값을 키라고 부릅니다. 이 문서에서는 키가 작을수록 급합니다.

우선순위 큐를 만드는 가장 흔한 방법은 힙입니다. 힙은 항목을 트리 모양으로 담습니다. 트리는 항목을 위에서 아래로 가지 치듯 매달아 두는 구조입니다.

트리의 항목 하나를 노드라고 부릅니다. 한 노드 바로 아래에 매달린 노드는 자식, 바로 위의 노드는 부모입니다. 같은 부모를 둔 노드끼리는 형제입니다. 맨 위에 있어 부모가 없는 노드는 뿌리입니다.

힙은 부모의 키가 언제나 자식의 키보다 작거나 같게 둡니다. 이 규칙을 힙 순서라고 부릅니다. 이 규칙 덕분에 트리에서 가장 작은 키는 늘 뿌리에 있습니다.

우선순위 큐의 기본 동작은 셋입니다. 넣기, 최솟값 꺼내기, 꺼내지 않고 들여다보기만 하는 최솟값 보기입니다.

여기에 하나가 더 있습니다. 이미 들어 있는 항목의 키를 더 작게 바꾸는 키 줄이기(decrease-key)입니다. 넣어 둔 항목이 뒤늦게 더 급해졌을 때 부릅니다.

키 줄이기를 가장 많이 부르는 곳은 다익스트라 알고리즘입니다. 이 알고리즘은 지도의 교차로 같은 지점마다 출발점에서의 거리를 키로 두고 우선순위 큐에 넣습니다. 더 짧은 길이 발견될 때마다 그 지점의 거리를 줄입니다. 길이 많은 지도일수록 이 호출이 꺼내기보다 훨씬 많아집니다.

이진 힙이 치르는 비용

연산 비용은 빅오 표기법으로 적습니다. 항목이 n 개일 때 시간이 n 을 따라 얼마나 늘어나는지만 보는 표기입니다. O(1) 은 n 과 상관없이 일정합니다. O(log n) 은 n 이 두 배가 될 때마다 1씩만 늘어납니다.

이진 힙은 한 노드가 자식을 둘까지 두는 힙을 배열 하나에 담은 것입니다. 넣기와 키 줄이기는 항목을 부모와 맞바꾸며 위로 올려 보내는 방식으로 합니다. 트리 높이가 log n 안팎이라 한 번에 O(log n) 이 듭니다.

키 줄이기 한 번이 O(log n) 이면 작아 보입니다. 하지만 다익스트라 알고리즘은 길 하나마다 키 줄이기를 한 번씩 부를 수 있습니다. 길이 백만 개면 O(log n) 짜리 호출이 백만 번 쌓입니다.

두 힙을 하나로 합치는 일도 이진 힙은 느립니다. 배열 둘을 이어 붙인 뒤 힙 순서를 다시 세워야 해서 O(n) 이 듭니다.

피보나치 힙은 넣기·키 줄이기·두 힙 합치기를 O(1) 로 낮춥니다. 대가로 정리할 일을 최솟값 꺼내기 한 연산에 몰아 둡니다.

여러 그루의 트리를 묶은 모양

피보나치 힙은 트리 하나가 아니라 여러 그루의 트리를 묶어 둡니다. 트리마다 힙 순서를 지킵니다. 트리끼리는 아무 순서도 없습니다.

노드끼리는 포인터로 잇습니다. 포인터는 다른 노드가 메모리 어디에 있는지 가리키는 값입니다. 이진 힙이 칸 번호 계산으로 부모와 자식을 찾는 것과 다릅니다.

각 트리의 뿌리는 뿌리 목록이라는 연결 리스트에 줄지어 있습니다. 이 목록을 따라가면 힙에 든 트리를 모두 만납니다.

힙 전체에서 가장 작은 키는 어느 한 트리의 뿌리에 있습니다. 힙은 그 뿌리를 가리키는 최솟값 포인터를 따로 들고 있습니다. 최솟값 보기는 이 포인터 하나만 읽으면 끝나 O(1) 입니다.

아래는 트리 세 그루로 된 피보나치 힙입니다. 노드 안의 숫자는 키입니다.

flowchart TD
    M["최솟값 포인터"] --> R2
    subgraph roots["뿌리 목록"]
        R1["7"]
        R2["3"]
        R3["17"]
    end
    R2 --> A["18"]
    R2 --> B["52"]
    A --> C["39"]
    R3 --> D["30"]

트리마다 부모가 자식보다 작습니다. 그러나 뿌리 7 과 3 과 17 사이에는 순서가 없습니다. 최솟값 포인터는 세 뿌리 가운데 가장 작은 3 을 가리킵니다.

노드 하나는 키 말고도 포인터 여럿과 작은 값 둘을 들고 있습니다.

차수와 표시는 뒤의 소절에서 쓰임을 봅니다. 먼저 왼쪽·오른쪽 포인터를 봅니다.

형제끼리는 양쪽 방향으로 잇습니다. 맨 끝과 맨 처음도 이어서 원을 만듭니다. 이런 목록을 원형 이중 연결 리스트라고 부릅니다.

아래는 부모 하나와 자식 셋의 포인터입니다. 부모는 자식 칸으로 자식 하나만 가리킵니다. 나머지 자식은 왼쪽·오른쪽 칸을 따라가 만납니다.

flowchart TD
    P["부모"] -->|"자식 칸"| A["자식 1"]
    A <-->|"왼쪽 · 오른쪽 칸"| B["자식 2"]
    B <-->|"왼쪽 · 오른쪽 칸"| C["자식 3"]
    C <-->|"왼쪽 · 오른쪽 칸"| A
    A -.->|"부모 칸"| P
    B -.->|"부모 칸"| P
    C -.->|"부모 칸"| P

원형 이중 연결 리스트로 이으면 목록 둘을 이어 붙이거나 노드 하나를 빼는 일이 포인터 몇 개만 바꿔 O(1) 에 끝납니다. 뿌리 목록도 같은 원형 이중 연결 리스트입니다.

넣기와 두 힙 합치기

넣기는 노드 하나짜리 트리를 새로 만들어 뿌리 목록에 붙이면 끝납니다. 새 키가 지금의 최솟값보다 작으면 최솟값 포인터만 옮깁니다. 다른 트리와 견주지 않으므로 O(1) 입니다.

두 힙 합치기도 같은 식입니다. 두 뿌리 목록을 이어 붙입니다. 두 최솟값 가운데 작은 쪽을 새 최솟값 포인터로 삼습니다. 원형 목록 둘을 잇는 데는 포인터 네 개만 바꾸면 됩니다.

넣기만 되풀이하면 뿌리 목록은 노드 하나짜리 트리로 길게 늘어납니다. 값 4·9·2·7·6 을 차례로 넣으면 뿌리가 다섯 개인 힙이 됩니다. 이 힙은 다음 소절의 예로 씁니다.

최솟값 꺼내기와 뿌리 정리

최솟값 꺼내기는 미뤄 둔 정리를 몰아서 하는 연산입니다. 순서는 셋입니다.

1. 최솟값 포인터가 가리키는 뿌리를 뿌리 목록에서 뺍니다
2. 그 뿌리의 자식들을 전부 뿌리 목록에 올립니다
3. 뿌리 목록을 정리하고 새 최솟값을 찾습니다

셋째 단계의 뿌리 정리가 핵심입니다. 뿌리 정리는 차수가 같은 뿌리 둘을 찾아 하나로 잇는 일을 되풀이합니다. 잇기는 키가 큰 뿌리를 키가 작은 뿌리의 자식으로 붙이는 것입니다. 작은 쪽이 위에 오니 힙 순서가 지켜집니다.

차수가 같은 뿌리를 빨리 찾으려고 차수별 칸을 가진 표를 하나 씁니다. 뿌리 목록을 한 바퀴 돌며 뿌리를 제 차수의 칸에 넣습니다.

그 칸에 이미 다른 뿌리가 있으면 둘을 잇습니다. 이은 트리는 차수가 1 늘었으니 다음 칸으로 옮깁니다. 원래 칸은 비웁니다.

앞에서 4·9·2·7·6 을 넣은 힙으로 따라가 봅니다. 아래가 꺼내기 전의 모양입니다.

flowchart TD
    M["최솟값 포인터"] --> C
    subgraph roots["뿌리 목록"]
        A["4"]
        B["9"]
        C["2"]
        D["7"]
        E["6"]
    end

2 를 꺼냅니다. 2 는 자식이 없어 올릴 노드가 없습니다. 남은 뿌리 4·9·7·6 을 차례로 정리합니다.

차례 4 를 마친 때의 표를 그려 봅니다. 차수 0 칸은 비었습니다. 차수 1 칸에는 4 가 9 를 달고 있습니다. 여기에 6 이 7 을 달고 차수 1 로 막 올라왔습니다.

flowchart TD
    subgraph K0["차수 0 칸"]
        Z["비어 있음"]
    end
    subgraph K1["차수 1 칸"]
        A["4"] --> B["9"]
    end
    subgraph NEW["차수 1 로 막 올라온 트리"]
        E["6"] --> D["7"]
    end
    Z ~~~ A
    B ~~~ E

차수 1 트리가 둘이 되었으니 차례 5 에서 둘을 잇습니다. 키가 큰 6 이 4 아래로 갑니다.

잇기가 세 번 일어나 트리가 한 그루로 줄었습니다. 새 최솟값은 남은 뿌리 가운데 가장 작은 4 입니다.

flowchart TD
    M["최솟값 포인터"] --> A
    subgraph roots["뿌리 목록"]
        A["4"]
    end
    A --> B["9"]
    A --> E["6"]
    E --> D["7"]

차수가 같은 트리끼리 이어 차수가 겹치지 않게 만드는 방식은 이항 힙과 같습니다. 이항 힙은 이 정리를 넣을 때마다 합니다. 피보나치 힙은 꺼낼 때까지 미룹니다.

정리가 끝나면 뿌리마다 차수가 다릅니다. 뒤에서 보듯 차수는 O(log n) 을 넘지 못하므로 남는 뿌리도 O(log n) 개입니다.

꺼내기 한 번은 느릴 수 있습니다. 넣기만 n 번 한 뒤 처음 꺼내면 뿌리 n 개를 모두 정리해야 해서 O(n) 이 듭니다. 대신 그 뒤의 꺼내기는 뿌리가 몇 개 안 남아 빨라집니다.

분할 상환으로 세는 비용

피보나치 힙의 비용은 연산 한 번의 최악으로 적지 않습니다. 연산을 여러 번 이어 할 때 한 번에 평균 얼마가 드는지로 적습니다. 이 값을 분할 상환 비용이라고 부릅니다.

이 평균은 확률로 구한 기대값이 아닙니다. 어떤 순서로 연산을 불러도 합계가 「이 값 × 연산 수」를 넘지 않는다는 보장입니다. 앞 소절의 O(n) 짜리 꺼내기도 앞선 넣기 n 번과 묶어 세면 한 번에 상수 몫이 됩니다.

이 소절이 보이려는 것은 하나입니다. 꺼내기가 몰아서 하는 정리 비용을, 뿌리를 쌓아 둔 넣기에 미리 나눠 셀 수 있다는 것입니다. 근거는 두 사실입니다.

첫째, 뿌리 정리는 뿌리 목록의 뿌리를 하나씩 봅니다. 정리 한 번에 드는 일은 목록에 쌓인 뿌리 수에 비례합니다.

둘째, 한 번 이어진 뿌리는 자식이 되어 뿌리 목록에서 빠집니다. 다음 정리에서 다시 세지 않습니다. 뿌리 하나가 정리에 드는 일은 한 번뿐입니다.

그러니 넣기 한 번의 비용을 「노드를 붙이는 일 + 그 노드를 나중에 정리할 일」로 셉니다. 둘 다 상수라 넣기는 여전히 O(1) 입니다. 꺼내기가 따로 치르는 것은 자기가 올린 자식들과 정리 뒤 남는 뿌리뿐입니다. 둘 다 최대 차수를 넘지 못해 O(log n) 입니다.

키 줄이기와 잘라내기

키 줄이기는 노드의 키를 작게 바꿉니다. 바뀐 키가 부모의 키보다 여전히 크거나 같으면 할 일이 없습니다. 부모보다 작아지면 힙 순서가 깨집니다.

이진 힙은 이때 노드를 부모와 맞바꾸며 위로 올립니다. 피보나치 힙은 올리지 않습니다.

대신 그 노드를 부모에게서 떼어 자기 아래 트리째 뿌리 목록에 올립니다. 뿌리에는 부모가 없으니 힙 순서가 다시 맞습니다. 이것을 잘라내기라고 부릅니다.

잘라내기만 하면 트리가 한없이 앙상해질 수 있습니다. 어떤 노드의 자식들이 저마다 자기 자식을 잃는다고 해 봅니다. 그 노드의 차수는 그대로입니다. 아래에 딸린 노드 수만 줄어듭니다.

이런 일이 쌓이면 노드 수에 비해 차수가 큰 트리가 생깁니다. 그러면 뒤에서 볼 차수의 상한이 무너집니다.

그래서 노드마다 표시라는 칸을 둡니다. 표시는 이 노드가 뿌리가 아닌 채로 자식을 하나 잃었다는 기록입니다. 자식을 처음 잃으면 표시를 켭니다. 표시가 켜진 노드가 자식을 하나 더 잃으면 그 노드도 잘라 뿌리 목록에 올립니다.

잘려 올라간 노드의 부모도 표시가 켜져 있었다면 같은 일이 이어집니다. 표시가 꺼진 부모나 뿌리를 만날 때까지 위로 거슬러 올라갑니다. 이를 연쇄 잘라내기(cascading cut)라고 부릅니다. 뿌리 목록에 올라간 노드는 표시를 끕니다.

키 줄이기 한 번의 갈림을 모으면 아래와 같습니다. 부모의 표시가 꺼져 있으면 표시만 켜고 멈춥니다. 그림의 「부모의 표시를 켜고 끝」 갈래입니다.

flowchart TD
    S["노드의 키를 줄인다"] --> Q1{"부모보다 작아졌나"}
    Q1 -->|"아니다"| X["끝"]
    Q1 -->|"그렇다"| C["그 노드를 잘라 뿌리 목록에 올리고 표시를 끈다"]
    C --> Q2{"잘린 노드의 부모가 뿌리인가"}
    Q2 -->|"그렇다"| X
    Q2 -->|"아니다"| Q3{"부모의 표시가 켜져 있나"}
    Q3 -->|"아니다"| Y["부모의 표시를 켜고 끝"]
    Q3 -->|"그렇다 · 부모를 그 노드로 삼는다"| C

아래 트리에서 20 을 3 으로 줄여 봅니다. 「표시」라고 적은 노드는 이미 자식을 하나 잃은 노드입니다.

flowchart TD
    subgraph roots["뿌리 목록"]
        R["1"]
    end
    R --> A["5 · 표시"]
    R --> B["8"]
    A --> C["12 · 표시"]
    A --> E["9"]
    C --> D["20"]
    C --> F["15"]

3 은 부모 12 보다 작으므로 잘려 뿌리가 됩니다. 12 는 표시가 켜져 있었으므로 자식 15 를 단 채 잘려 뿌리가 됩니다. 12 의 부모 5 도 표시가 켜져 있어 9 를 단 채 잘립니다. 5 의 부모 1 은 뿌리라서 연쇄가 멈춥니다.

flowchart TD
    subgraph roots["뿌리 목록"]
        R["1"]
        A["5"]
        C["12"]
        D["3"]
    end
    R --> B["8"]
    A --> E["9"]
    C --> F["15"]

뿌리가 넷으로 늘었습니다. 올라간 노드들의 표시는 모두 꺼졌습니다. 3 은 1 보다 크니 최솟값 포인터는 계속 1 을 가리킵니다.

연쇄가 길면 키 줄이기 한 번이 여러 노드를 자릅니다. 그런데 연쇄로 잘리는 노드는 모두 표시가 켜져 있던 노드입니다. 이 노드들은 잘리면서 표시가 꺼집니다.

표시는 키 줄이기 한 번에 많아야 하나 켜집니다. 연쇄의 길이를 모두 더해도 그동안의 키 줄이기 횟수를 넘지 못하는 까닭입니다.

이 셈으로 키 줄이기는 분할 상환 O(1) 입니다. 늘어난 뿌리는 다음 꺼내기의 뿌리 정리가 거둬들입니다.

항목 지우기는 키 줄이기와 꺼내기를 이어 붙여 만듭니다. 지울 노드의 키를 어떤 키보다도 작게 줄여 최솟값으로 만든 뒤 꺼냅니다. 비용은 꺼내기와 같은 분할 상환 O(log n) 입니다.

키 줄이기를 부르려면 그 항목이 든 노드의 포인터를 호출하는 쪽이 들고 있어야 합니다. 힙에는 키로 노드를 찾는 기능이 없습니다. 뒤져서 찾으면 O(n) 이 듭니다.

그래서 넣기가 새 노드의 포인터를 돌려줍니다. 호출하는 쪽은 그 포인터를 보관했다가 키 줄이기에 넘깁니다.

차수의 상한과 피보나치라는 이름

뿌리 정리가 끝나면 차수마다 뿌리가 많아야 하나씩 남습니다. 꺼내기의 비용은 노드 하나가 가질 수 있는 최대 차수에 달려 있습니다. 표시 규칙은 이 최대 차수를 O(log n) 으로 묶어 둡니다.

까닭은 두 규칙에서 나옵니다. 첫째, 잇기는 차수가 같은 두 뿌리끼리만 일어납니다.

어떤 노드에 i 번째 자식이 붙는 순간을 봅니다. 그 노드에는 먼저 붙은 자식이 적어도 i−1 개 있었으니 차수가 적어도 i−1 입니다. 차수가 같은 뿌리끼리만 이으니 붙는 자식의 차수도 적어도 i−1 이었습니다.

둘째, 뿌리가 아닌 노드는 자식을 하나까지만 잃고 버팁니다. 둘째를 잃으면 잘려 나가기 때문입니다. 그래서 i 번째 자식의 차수는 지금도 적어도 i−2 입니다.

이 조건으로 차수마다 트리에 노드가 적어도 몇 개 있는지 셀 수 있습니다. 아래는 차수가 4 인 뿌리가 가장 앙상할 때의 모양입니다. 자식 넷의 차수가 차례로 0·0·1·2 입니다.

flowchart TD
    R["뿌리 · 차수 4"] --> A["자식 1 · 차수 0"]
    R --> B["자식 2 · 차수 0"]
    R --> C["자식 3 · 차수 1"]
    R --> D["자식 4 · 차수 2"]
    C --> C1["노드"]
    D --> D1["노드"]
    D --> D2["노드"]

뿌리까지 세면 노드가 여덟 개입니다. 자식 3 아래는 차수 1 짜리 가장 작은 트리입니다. 자식 4 아래는 차수 2 짜리 가장 작은 트리입니다.

이 트리에서 자식 4 와 그 아래를 떼어 내 봅니다. 남은 뿌리와 자식 셋은 차수 3 짜리 가장 작은 트리입니다. 노드는 다섯 개입니다. 떼어 낸 쪽은 차수 2 짜리 가장 작은 트리로 노드가 세 개입니다. 8 = 5 + 3 입니다.

어느 차수에서나 같은 일이 일어납니다. 차수 k 의 가장 작은 트리는 차수 k−1 의 가장 작은 트리 뿌리 아래에 차수 k−2 의 가장 작은 트리를 매단 것입니다. 그래서 최소 노드 수가 앞의 두 값을 더하며 자랍니다.

아래는 차수 0 부터 3 까지의 가장 작은 트리입니다. 차수 2 와 3 은 어느 부분이 한 차수 앞의 트리이고 어느 부분이 두 차수 앞의 트리인지 칸으로 갈랐습니다.

flowchart TD
    subgraph T0["차수 0 · 노드 1개"]
        a0["뿌리"]
    end
    subgraph T1["차수 1 · 노드 2개"]
        b0["뿌리"] --> b1["자식"]
    end
    subgraph T2["차수 2 · 노드 3개"]
        subgraph T2a["차수 1 가장 작은 트리"]
            c0["뿌리"] --> c1["자식"]
        end
        subgraph T2b["차수 0 가장 작은 트리"]
            c2["자식"]
        end
        c0 --> c2
    end
    subgraph T3["차수 3 · 노드 5개"]
        subgraph T3a["차수 2 가장 작은 트리"]
            d0["뿌리"] --> d1["자식"]
            d0 --> d2["자식"]
        end
        subgraph T3b["차수 1 가장 작은 트리"]
            d3["자식"] --> d4["노드"]
        end
        d0 --> d3
    end
    a0 ~~~ b0
    b1 ~~~ c0
    c2 ~~~ d0

차수 1 은 뿌리 하나에 자식 하나라 1 + 1 = 2 입니다. 차수 2 는 2 + 1 = 3 입니다. 차수 3 은 3 + 2 = 5 입니다. 차수 4 가 앞에서 본 5 + 3 = 8 입니다.

피보나치 수열은 1, 1, 2, 3, 5, 8, 13 처럼 앞의 두 수를 더해 다음 수를 만드는 수열입니다. 차수별 최소 노드 수가 이 수열을 따릅니다.

차수 0 트리의 노드 1 개는 수열의 두 번째 1 에 해당합니다. 차수 1 이 1 + 1 = 2 로 시작하기 때문입니다. 아래 표가 수열보다 한 칸 밀려 1, 2, 3 으로 시작하는 까닭이 이것입니다.

피보나치 수는 한 항마다 약 1.618 배씩 커집니다. 이 비율을 황금비라고 부릅니다. 노드 수가 차수에 대해 거듭제곱으로 불어나니, 거꾸로 차수는 노드 수 n 의 로그를 넘지 못합니다.

최대 차수가 O(log n) 인 까닭이 이것입니다. 이 구조가 피보나치라는 이름을 얻은 까닭도 같습니다.

연산별 비용

지금까지 본 비용을 이진 힙과 나란히 놓습니다. 이진 힙 칸은 연산 한 번의 최악입니다. 피보나치 힙 칸은 분할 상환 비용입니다.

꺼내기와 지우기만 보면 둘이 같습니다. 차이는 넣기·키 줄이기·합치기에서 납니다. 이 셋을 꺼내기보다 훨씬 많이 부르는 계산일수록 차이가 커집니다.

공간은 둘 다 항목 수에 비례하는 O(n) 입니다. 그래도 노드 하나에 드는 메모리는 크게 다릅니다. 이진 힙은 배열 칸 하나에 항목만 담습니다. 피보나치 힙 노드는 포인터 넷과 차수·표시를 더 담습니다.

다익스트라 알고리즘에서 얻는 것

그래프는 지점과 그 사이를 잇는 길로 이루어진 구조입니다. 지점을 정점, 길을 간선이라고 부릅니다. 정점 수를 V, 간선 수를 E 로 적습니다.

다익스트라 알고리즘은 최솟값 꺼내기를 정점마다 한 번 부릅니다. 키 줄이기는 간선마다 많아야 한 번 부릅니다. 이진 힙으로 짜면 두 연산이 모두 O(log V) 라서 전체가 O((V+E) log V) 입니다.

피보나치 힙으로 짜면 키 줄이기가 O(1) 이 됩니다. 전체는 O(E + V log V) 로 줄어듭니다. 간선 쪽 항에서 log V 가 빠진 것입니다.

간선이 정점보다 훨씬 많은 그래프일수록 차이가 벌어집니다. 정점 천 개가 서로 거의 다 이어진 그래프라면 간선은 수십만 개입니다. 이진 힙은 그 수십만 번마다 log V 를 치릅니다. 피보나치 힙은 상수만 치릅니다.

프림 알고리즘도 같은 모양으로 키 줄이기를 부릅니다. 프림 알고리즘은 그래프의 모든 정점을 간선 길이의 합이 가장 작게 잇는 최소 신장 트리를 찾습니다. 피보나치 힙을 쓰면 이 알고리즘도 O(E + V log V) 가 됩니다.

실무 코드에서 드문 까닭

비용표로는 피보나치 힙이 앞섭니다. 그래도 실무 코드에서는 드뭅니다. 빅오 표기는 상수배를 지우고 적은 값입니다. 연산 하나에 드는 일의 양은 표에 드러나지 않습니다.

노드마다 포인터가 넷이라 메모리를 많이 씁니다. 노드가 메모리 여기저기에 흩어져 있어 포인터를 따라갈 때마다 캐시 메모리에서 빗나가기 쉽습니다. 이진 힙은 배열 하나에 붙어 있어 이웃 칸을 연달아 읽습니다. 이 차이 때문에 흔한 크기의 입력에서는 이진 힙이 더 짧은 시간에 끝나는 경우가 많습니다.

코드도 깁니다. 원형 목록 잇기, 차수별 표, 표시와 연쇄 잘라내기를 모두 맞게 짜야 합니다.

표준 라이브러리가 내놓는 우선순위 큐도 대개 배열에 담은 힙입니다. 파이썬의 heapq 는 리스트 하나에 담은 이진 힙입니다. 자바의 PriorityQueue 도 넣기와 꺼내기에 O(log n) 이 드는 힙입니다.

키 줄이기를 아예 안 쓰는 방법도 흔합니다. 키가 줄면 같은 항목을 새 키로 한 번 더 넣습니다. 꺼낸 항목이 이미 처리한 것이면 버립니다. 이 방법이면 이진 힙만으로 다익스트라 알고리즘을 짤 수 있습니다.

키 줄이기와 합치기가 잦은 계산에서 코드를 짧게 두고 싶으면 페어링 힙을 고르기도 합니다. 피보나치 힙은 주로 다익스트라 알고리즘과 프림 알고리즘의 비용 상한을 O(E + V log V) 까지 낮출 수 있음을 보이는 데 쓰입니다.

관련 항목

피보나치 힙이 속하는 상위 분류

자료구조 · 힙 (자료구조) · 우선순위 큐 · 추상 자료형 · 트리

피보나치 힙과 같은 역할을 두고 겨루는 힙

이진 힙 · 이항 힙 · 페어링 힙 · d-ary 힙 · 레프티스트 힙 · 스큐 힙 · 브로달 큐

피보나치 힙을 이루는 구성 요소

노드 · 포인터 · 연결 리스트 · 원형 연결 리스트 · 이중 연결 리스트

피보나치 힙을 부르는 알고리즘

다익스트라 알고리즘 · 프림 알고리즘 · 최단 경로 · 최소 신장 트리 · 그래프 · 정점 (그래프) · 간선

피보나치 힙의 비용을 따지는 이론

분할 상환 비용 · 퍼텐셜 함수 · 빅오 표기법 · 시간 복잡도 · 피보나치 수열 · 황금비

피보나치 힙의 실행 속도를 좌우하는 메모리 성질

CPU 캐시 · 참조 지역성 · 캐시 미스 · 동적 메모리 할당