비워 두어서 더 빨라지는 힙

1편의 이진 힙은 배열과 완전 이진 트리라는 단순한 조합으로 훌륭한 우선순위 큐를 만든다. find-min은 O(1), insert와 delete-min은 O(log n)이다. 대부분의 소프트웨어에서는 이진 힙이 좋은 기본 선택이다.

하지만 Dijkstra 알고리즘처럼 힙 안에 이미 들어 있는 item의 key를 자주 낮추는 작업에서는 병목이 달라진다.

• 핸들을 지원하는 이진 힙도 decrease-key 때 배열 원소를 위로 교환하므로 O(log n)이 걸린다.
• C++ std::priority_queue에는 item 핸들, decrease-key, meld가 없다.
• Fibonacci Heap은 decrease-key를 O(1) 상각 시간에 처리하지만, cut·mark·cascading cut을 관리해야 한다.

Hansen, Kaplan, Tarjan, Zwick의 Hollow Heap은 다른 질문을 던진다.

key를 낮춘 item을 새 node로 옮기고, 이전 node는 비워 둔 채 나중에 정리하면 어떨까?

그림 1. 이진 힙은 갱신 즉시 구조를 복구한다. Hollow Heap은 item 이동과 몇 번의 link만 수행하고, hollow node 제거를 delete-min으로 미룬다.

이 글은 논문의 최종 형태인 two-parent Hollow Heap을 중심으로 다룬다. 목표는 의사 코드만 외우는 것이 아니라, 왜 이 작은 지연 전략이 Fibonacci Heap과 같은 상각 시간 경계를 만드는지 이해하는 것이다.

난이도: ⭐⭐⭐⭐

선행 지식: 최소 힙, 트리와 DAG, Big-O, 상각 분석의 기본 개념

학습 포인트: item/node 분리, heap-ordered DAG, ranked link, Fibonacci rank 경계, potential method

1. item과 node를 분리한다

일반적인 힙 설명에서는 “원소”와 “노드”를 같은 것으로 취급한다. Hollow Heap에서는 둘을 엄격히 나눈다.

• item: 사용자가 넣은 실제 객체다. key와 현재 node를 찾는 핸들을 가진다.
• full node: 현재 item 하나를 담고 있는 node다.
• hollow node: item이 떠나 비어 있는 node다.
• key of a node: full node에서는 현재 item의 key이고, hollow node에서는 item이 떠나기 직전의 key다.

한번 hollow가 된 node는 다시 full이 되지 않는다. 구조 안에는 남아 있을 수 있지만 사용자가 찾는 item은 이미 다른 node로 이동했거나 삭제됐다.

이 구분이 중요한 이유는 논리적 값의 이동과 물리적 연결 구조의 변경을 분리하기 때문이다. decrease-key는 item만 새 node로 옮긴다. 이전 node의 자식과 link 이력은 당장 건드리지 않는다.

반드시 유지할 기본 불변식

two-parent 버전은 다음 상태를 유지한다.

1. 비어 있지 않은 heap은 하나의 full root를 가진다.
2. 어떤 실제 arc (v, w)에도 v.key ≤ w.key가 성립한다.
3. full node의 부모는 최대 하나, hollow node의 부모는 최대 둘이다.
4. hollow root는 정상 상태에 남지 않는다. 최소 item 삭제 중에 생기면 정리 과정에서 파괴한다.

2번 때문에 root의 item이 전체 최솟값이다. 3번은 decrease-key가 기존 node에 새 부모를 하나 더 붙일 수 있게 해 주면서도 DAG의 연결 수가 통제되도록 한다.

2. one-parent에서 two-parent DAG까지

논문은 Hollow Heap을 한 번에 DAG로 제시하지 않고 세 형태로 전개한다.

다중 루트 one-parent 버전

heap-ordered tree들의 forest를 유지한다. decrease-key로 old node u를 hollow로 만들 때, rank 규칙에 맞춰 일부 자식과 그 subtree를 새 node v로 옮긴다. 자식 목록을 rank 내림차순으로 두면 옮길 부분을 O(1)에 잘라 낼 수 있다.

단일 루트 one-parent 버전

서로 다른 rank의 root도 unranked link할 수 있게 하여 하나의 heap-ordered tree를 유지한다. meld와 decrease-key가 끝날 때 root는 하나다. 다만 여전히 u의 일부 자식을 v로 옮겨야 한다.

two-parent 버전

자식을 전혀 옮기지 않는다. 대신 old node u 자체를 new node v의 자식으로 만든다. u가 원래 부모를 가지고 있었다면 이제 부모가 둘이므로 구조는 tree가 아니라 heap-ordered DAG가 된다.

이 선택은 단순한 구현 요령 이상의 의미가 있다. 미래에 u와 v 중 어느 쪽이 먼저 파괴될지는 알 수 없다. one-parent 방식에서는 자식을 둘 사이에 분배하므로 먼저 파괴된 쪽의 자식들이 root로 노출된다. two-parent 방식에서는 u의 기존 자식들이 두 부모가 모두 정리될 때까지 노출되지 않을 수 있다. 논문은 이것을 국소적 장점으로 설명하지만, 전체 실행 시간에서 항상 더 빠른지는 실험 문제로 남긴다.

3. decrease-key: cascading cut 대신 clone을 남긴다

item X가 key 8, rank 4인 node u에 있고, 새 key가 3이라고 하자. u가 root가 아니라면 two-parent decrease-key는 다음 순서로 진행된다.

1. key 3인 새 full node v를 만든다.
2. X를 u에서 v로 옮긴다. 이제 u는 hollow다.
3. v.rank = max(0, u.rank - 2) = 2로 정한다.
4. u를 v의 자식으로 만든다. u의 기존 자식은 하나도 옮기지 않는다.
5. v와 기존 full root를 link하여 key가 작은 쪽을 root로 만든다.

그림 2. 굵은 선은 ranked link, 보라색 점선은 unranked link, 황색 점선은 decrease-key로 생긴 두 번째 부모 관계다. 결과는 하나의 full root를 가진 DAG다.

새 arc는 (v, u)이고 v.key = 3 ≤ 8 = u.key이므로 heap order가 유지된다. 새 node 하나, item 핸들 변경, 고정 개수의 포인터 변경과 link 한 번만 필요하다. 따라서 root가 아닌 item의 decrease-key는 **최악 O(1)**이다. item이 최소 root에 있다면 새 node도 만들지 않고 root key만 낮추면 된다.

왜 Fibonacci Heap의 cascading cut이 필요하지 않은가?

Fibonacci Heap은 기존 node의 key를 제자리에서 낮춘다. 부모보다 작아지면 node를 잘라 root list로 보내고, 부모의 자식 손실 상태에 따라 조상 방향으로 cascading cut을 수행한다. mark bit는 “이미 자식을 하나 잃었는가?”를 기록한다.

Hollow Heap은 위반 가능성이 있는 item을 새 위치로 복제하듯 이동한다. old node를 hollow로 두면 기존 부모-자식 비교 결과가 그대로 유효하다. subtree를 잘라 올릴 이유가 없고, 조상에게 자식 손실을 전파할 이유도 없다.

정확히 말하면 node가 복제되는 것이 아니라 같은 item을 시간에 따라 담았던 node들이 생긴다. 논문은 이 node들을 clones라고 부른다. 한 item의 clones는 최신 node에서 과거 node로 이어지는 DAG 경로를 이루며, 최신 node를 제외하면 모두 hollow다.

4. ranked link와 unranked link

Hollow Heap의 link는 목적에 따라 두 종류다.

두 link 모두 패자를 승자의 자식으로 만든다. 차이는 rank 증가 여부다. rank는 단순한 트리 높이가 아니라, 과거 ranked link로 확보한 구조적 크기의 인증서에 가깝다.

rank - 2 규칙은 왜 필요한가?

rank r인 정상 node는 분석상 rank 0, 1, ..., r-1인 가상 자식을 하나씩 가진다. decrease-key로 rank r인 u가 hollow가 되면 새 node v의 rank를 max(0, r-2)로 정한다.

이 규칙은 양쪽에 필요한 증거를 남긴다.

• 새 node v는 낮은 rank 쪽의 구조를 이어받은 것으로 분석할 수 있다.
• old hollow node u에는 가장 높은 두 rank r-2, r-1의 가상 자식이 남는다.

two-parent 구현은 실제 자식을 옮기지 않으므로 이 “이어받음”은 포인터 조작이 아니다. 증명을 위해 각 node에 하나의 virtual parent를 지정하여, one-parent 버전에서 자식을 옮긴 것과 같은 효과를 추적한다.

그림 3. 가상 간선은 분석 도구일 뿐 실제 DAG 포인터가 아니다. 높은 두 rank의 가상 subtree가 남기 때문에 rank가 구조 크기보다 과도하게 커질 수 없다.

Fibonacci 수가 등장하는 이유

rank r node의 가상 후손 수를 S(r)라 하자. full인지 hollow인지와 무관하게 rank r-1, r-2인 두 가상 자식의 구조가 보존되므로

S(r) ≥ 1 + S(r - 1) + S(r - 2)

가 성립한다. 따라서 논문의 Lemma 4.6처럼

S(r) ≥ F(r + 3) - 1

이고, F(r + 2) ≥ φ^r이므로 node가 총 N개일 때

rank ≤ logφ N = O(log N)

이다. 여기서 N은 full과 hollow를 모두 포함한 node 수다. 살아 있는 item 수 n만 세는 것이 아니다.

5. delete-min: 미룬 일을 한 번에 정리한다

delete-min은 Hollow Heap에서 가장 많은 일이 일어나는 연산이다.

1. full root의 item을 제거해 root를 hollow로 만든다.
2. hollow root를 파괴하고 자식을 조사한다.
3. 새로 root가 된 hollow node도 계속 파괴한다.
4. 노출된 full roots를 rank별 배열에 모아 같은 rank끼리 ranked link한다.
5. rank마다 최대 하나 남은 roots를 unranked link하여 full root 하나를 만든다.

두 부모 node를 만났을 때

hollow child가 부모를 둘 가진 상태에서 한 부모가 파괴되면 즉시 root가 되지 않는다. 두 번째 부모 표시만 지우고 남은 부모 아래에 둔다. 부모를 하나만 가진 hollow child가 그 부모를 잃을 때에만 hollow root가 되어 정리 대상에 들어간다.

이 규칙이 DAG를 중복 순회하거나 아직 다른 부모에 연결된 subtree를 너무 일찍 노출하는 일을 막는다.

숫자로 따라가는 정리 예제

최소 root가 (key 1, rank 3)이고 그 아래에 hollow node H=(3,r2)가 있다고 하자. 1과 이어서 노출된 H를 파괴한 뒤 다음 full roots가 남았다고 가정한다.

(4,r0), (7,r0), (5,r1), (9,r1), (8,r2)

rank 배열을 이용한 통합은 이진 덧셈의 carry와 비슷하다.

1. (4,r0)과 (7,r0)을 ranked link한다. 4가 이겨 (4,r1)이 된다.
2. 이미 (5,r1)이 있으므로 다시 ranked link한다. 4가 이겨 (4,r2)가 된다.
3. 이미 (8,r2)가 있으므로 또 link한다. 4가 이겨 (4,r3)이 된다.
4. (9,r1)은 같은 rank 상대가 없으므로 남는다.
5. 마지막에 (4,r3)과 (9,r1)을 unranked link한다. 4가 root가 되고 rank는 3 그대로다.

그림 4. ranked link는 같은 rank의 충돌을 해결하며 승자 rank를 올린다. 마지막 unranked link는 서로 다른 rank를 묶되 rank를 바꾸지 않는다.

모든 root의 rank가 달라지면 root 수는 최대 rank 수에 비례한다. 최대 rank가 O(log N)이므로 마지막 unranked link 수도 O(log N)이다. 다만 한 번의 delete-min이 많은 hollow node를 실제로 파괴할 수 있으므로 이 연산의 경계는 **최악 시간이 아니라 상각 O(log N)**이다.

6. 상각 분석: 비용이 어디에 저장되는가

상각 분석은 “모든 delete-min이 싸다”는 주장이 아니다. 비싼 정리가 일어날 수 있지만, 그 비용을 앞선 연산이 만들어 둔 크레딧으로 지불할 수 있다는 주장이다.

6.1 hollow 파괴 비용

node는 insert마다 하나, root가 아닌 item의 decrease-key마다 하나 생성된다. 각 node는 최대 한 번 파괴된다. 따라서 hollow node를 방문하고 파괴하는 총비용은 그 node를 만든 연산에 O(1)씩 청구할 수 있다.

two-parent node가 한 부모를 잃고도 남는 사건도 각 decrease-key가 만든 두 번째 부모당 최대 한 번이다. 이 비용 역시 해당 decrease-key에 청구한다.

6.2 link 비용과 potential

논문의 two-parent 분석은 실제 DAG 위에 정의한 virtual-parent forest를 사용한다. 다음 full node마다 potential 1을 준다.

full node이면서, full node의 full virtual child가 아닌 node

그 밖의 node는 potential 0이다.

• ranked link는 full root 하나를 full node의 virtual child로 만든다. 실제 link 비용 1만큼 potential이 1 감소하므로 상각 비용이 상쇄된다.
• insert는 새 full node 하나를 만들어 potential을 상수만큼 늘린다.
• decrease-key도 새 full node와 virtual-child 상태 변화가 만드는 potential 증가가 상수로 제한된다.
• item 삭제로 full node가 hollow가 되면 그 node의 full virtual children이 potential 1을 얻을 수 있다. 그 수는 node rank 이하이고 최대 O(log N)이다.

그러므로 delete/delete-min에는 O(log N), 나머지 연산에는 O(1)의 상각 비용을 배정할 수 있다. 이것이 “정리를 미룬다”를 수학적으로 표현한 핵심이다.

potential은 구현 필드가 아니다. 실제 실행 중 저장하는 숫자가 아니라, 전체 연산열의 비용을 증명하기 위한 회계 장부다.

7. 연산별 복잡도와 n, N의 차이

• n: 현재 살아 있는 item 수
• N: 현재 구조에 남아 있는 full + hollow node 수

기본 Hollow Heap은 delete-min을 **O(log n)**이 아니라 **O(log N)**으로 분석한다. N은 지금까지 수행한 insert와 새 node를 만든 decrease-key 횟수의 영향을 받으며, N ≥ n이다.

rebuild의 시간·공간 trade-off

N > c·n이 되면 모든 hollow node를 제거하고 full node만으로 heap을 다시 만들 수 있다. rebuild는 O(N)이지만 제거되는 hollow node에 비용을 분산하면 다음 경계를 얻는다.

• delete와 delete-min: O(log n) 상각
• 나머지 연산: O(1) 상각
• 공간: O(n)

단, decrease-key가 rebuild를 직접 촉발하게 구현하면 그 한 번의 최악 O(1) 보장은 사라지고 상각 O(1)만 남는다. 논문은 incremental rebuild 또는 rebuild 시점을 delete 계열 연산으로 제한하는 변형도 논의한다. 실제로 rebuild할지는 메모리 제한과 workload를 측정해 결정해야 한다.

8. C++ 구현 스케치: 안정적인 Item 핸들이 핵심

아래 코드는 논문 Section 6의 decrease-key 핵심만 옮긴 축약 예시다. ep는 hollow node의 두 번째 부모를 가리킨다. 실제 구현에는 소유권 관리, 예외 안전성, 삭제된 핸들 검증, child-list 순회와 rank 배열 통합이 더 필요하다.

#include <algorithm>
#include <cassert>
 
struct Node;
 
struct Item {
    Node* node = nullptr;  // 현재 이 item을 담은 full node
};
 
struct Node {
    Item* item = nullptr;  // nullptr이면 hollow
    int key = 0;
    int rank = 0;
    Node* child = nullptr;
    Node* next = nullptr;
    Node* ep = nullptr;    // 두 부모일 때 두 번째 부모
};
 
void addChild(Node* child, Node* parent) {
    child->next = parent->child;
    parent->child = child;
}
 
Node* link(Node* a, Node* b) {
    if (b->key < a->key) {
        std::swap(a, b);
    }
    addChild(b, a);        // unranked link: a의 rank는 그대로
    return a;
}
 
Node* decreaseKey(Item& item, int newKey, Node* root) {
    Node* old = item.node;
    assert(old != nullptr && old->item == &item);
    assert(newKey <= old->key);
 
    if (old == root) {
        old->key = newKey; // 최소 root는 제자리 갱신 가능
        return root;
    }
 
    Node* fresh = new Node{
        .item = &item,
        .key = newKey,
        .rank = std::max(0, old->rank - 2),
        .child = old,
    };
 
    item.node = fresh;
    old->item = nullptr;   // old는 다시 full이 되지 않는다
    old->ep = fresh;       // fresh가 old의 두 번째 부모
 
    return link(fresh, root);
}

이 코드에서 Item의 주소는 heap에 들어 있는 동안 안정적이어야 한다. 예를 들어 std::vector<Item> 재할당으로 주소가 바뀌면 node의 Item*가 무효화된다. 안정적인 저장소, 객체 수명 정책, generation을 포함한 안전한 핸들 타입 등을 별도로 설계해야 한다.

std::priority_queue로 대신할 때의 주의점

std::priority_queue 내부 원소를 찾아 key를 직접 수정하는 것은 지원되지 않으며 heap invariant를 깨뜨릴 수 있다. 표준 어댑터는 iterator나 decrease-key 핸들도 제공하지 않는다.

실무에서는 흔히 새 (distance, vertex) 쌍을 다시 push하고, pop할 때 현재 거리와 다른 오래된 항목을 건너뛴다. 구현은 단순하지만 중복 항목만큼 메모리와 pop 횟수가 늘어난다. 이것은 Hollow Heap의 node/item 분리와 비슷한 지연 아이디어를 더 단순한 컨테이너 위에서 사용하는 방법이지, 진짜 decrease-key는 아니다.

9. Fibonacci Heap, 이진 힙과 정직하게 비교하기

Hollow Heap을 검토할 상황

• decrease-key와 meld가 매우 많고 그 복잡도 경계가 실제 설계를 좌우한다.
• Dijkstra, 최소 신장 트리, 최적 branching 등 고급 그래프 알고리즘의 이론 경계를 구현·연구한다.
• cascading cut 없이 Fibonacci 계열의 상각 분석을 학습하려 한다.
• item 핸들과 별도 node 수명 관리를 감당할 수 있다.

이진 힙이 더 나은 상황

• 필요한 연산이 push, top, pop 중심이다.
• 단순성, 작은 메모리 사용량, 캐시 지역성이 중요하다.
• 중복 삽입 후 stale entry를 건너뛰는 방식으로 충분하다.
• workload 측정 없이 “점근적으로 더 좋아 보인다”는 이유만으로 복잡한 힙을 도입하려 한다.

Hollow Heap이 Fibonacci Heap보다 항상 빠르다는 근거는 없다. 논문도 two-parent의 국소적 장점이 전역 성능 우위로 이어지는지는 열린 실험 문제라고 명시한다. 실제 선택은 연산 비율, allocator 비용, graph 밀도, 메모리 제한, 구현 품질을 벤치마크한 뒤 내려야 한다.

10. 불변식 중심으로 다시 보기

Hollow Heap의 핵심을 구현 관점에서 압축하면 다음과 같다.

1. heap order: 실제 모든 arc에서 부모 key가 자식 key 이하이다.
2. root 상태: 정상 상태에는 full root가 정확히 하나이고 hollow root가 없다.
3. 부모 수: full node는 최대 한 부모, hollow node는 최대 두 부모다.
4. rank 규칙: ranked link만 rank를 올리고, decrease-key의 새 rank는 max(0, old.rank - 2)다.
5. 크기 경계: rank r은 최소 F(r+3)-1개의 가상 후손을 요구하므로 O(log N)이다.
6. 지연 비용: node 생성과 두 번째 부모 손실은 생성 연산에, link는 potential 감소에 청구한다.

이 여섯 가지가 맞으면 decrease-key 때 자식을 옮기지 않아도 균형의 증거는 사라지지 않는다. Hollow Heap의 묘미는 실제 구조를 매번 정돈하는 대신, 나중에 정리해도 된다는 충분한 정보를 rank와 hollow 상태에 남기는 데 있다.

정리

• Hollow Heap은 item과 node를 분리하고, item이 떠난 node를 hollow로 남긴다.
• two-parent decrease-key는 새 full node를 만들고 old node를 그 자식으로 연결하여 최악 O(1)에 끝난다.
• 최종 구조는 tree나 forest가 아니라 하나의 full root를 가진 heap-ordered DAG다.
• ranked link는 같은 rank를 통합하고, unranked link는 rank를 바꾸지 않은 채 단일 root를 만든다.
• rank - 2 규칙은 Fibonacci형 가상 후손 경계를 보존하여 최대 rank를 O(log N)으로 제한한다.
• delete-min은 hollow를 파괴하고 roots를 rank별로 통합하며 상각 O(log N)이 걸린다.
• rebuild를 추가하면 O(log n) 상각 삭제와 O(n) 공간을 얻지만, 구현 방식에 따라 decrease-key의 최악 O(1) 보장을 잃을 수 있다.
• 이론적 장점과 실제 성능은 다르다. 일반적인 우선순위 큐의 기본 선택은 여전히 이진 힙이다.

다음 편에서는 Sinnamon–Tarjan 계열의 힙 설계를 통해 decrease-key와 구조 단순화의 다른 trade-off를 살펴볼 예정이다.

참고 자료

• Hansen, Kaplan, Tarjan, Zwick, “Hollow Heaps” (arXiv:1510.06535) — one-/two-parent 구조, rank invariant, virtual-parent 분석, 구현 의사 코드의 1차 출처
• Fredman, Tarjan, “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms” — Fibonacci Heap과 cascading cut의 원 논문
• cppreference: std::priority_queue — 표준 어댑터가 제공하는 공개 연산 확인