[자료구조] 이항 힙

위키피디아 : ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%ED%9E%99

이항 힙 - 위키백과, 우리 모두의 백과사전

이항 트리 시각화 사이트 : www.cs.usfca.edu/~galles/visualization/BinomialQueue.html

Binomial Queue Visualization

 

이항 힙은 이항 트리가 결합된 구조로 이루어져 있으며 n차수의 이항 트리는 2개의 n-1 차수 이항 트리 2개로 구성이 되어 있습니다. 위키피디아에서는 조금 다른 방식으로 설명하고 있습니다. 

- n자수의 이항트리의 루트 노드의 자식들은 각각 n-1, n-2, n-3... 2, 1 차수의 이항 트리로 구성되어 있습니다.

n차수의 이항 트리는 2^n개의 노드를 가지는 특성이 있습니다.

이항 트리

이항 힙

이 이항트리의 집합으로 구성된 것이 이항 힙입니다. 이진 힙과 유사하게 루트 노드가 가중치가 높은 노드가 되지만, 자식 노드는 2개 이상일 수 있습니다.  이항트리의 루트 노드들이 연결된 구조로 되어 있습니다. 이항 힙 구조에는 몇 가지의 조건이 있습니다. 

• 이항 힙을 구성하는 이항 트리의 루트 노드는 해당 이항 트리에서 가중치가 가장 높은 값을 가지고 있습니다. = 각각의 이항 트리는 heap 구조를 따릅니다.
• 이항 힙을 구성하는 이항 트리들의 차수는 차수별로 0개 또는 1개만을 가질 수 있습니다.

이항 힙

병합

힙에서 삽입, 삭제 등 연산을 하기 전에 대부분의 연산에서 사용하게 되는 기본 연산인 트리 병합을 먼저 알아보도록 하겠습니다. 이항 트리에서 병합은 같은 차수의 이항 트리를 병합하여 n+1 차수 이항 트리를 생성합니다. 처음 설명한 n차수의 이항트리는 2개의 n-1 차수 이항 트리 2개로 구성이 되어 있다는 특징을 생각하면 금방 이해하실 수 있습니다.

이항 트리 병합

루트 노드를 비교하고 가중치가 높은 노드를 가진 트리를 루트로 설정하고 가중치가 낮은 트리를 자식으로 설정합니다. 병합 시 자식 노드의 순서는 차수의 내림차순이기 때문에 앞에 삽입합니다. 단순히 루트 노드만을 비교하고 병합하기 때문에 걸리는 시간은 굉장히 작습니다. 이를 이용하여 삽입, 삭제 시 병합 연산을 이용하여 구현하게 됩니다.

 

삽입

삽입 연산은 간단하게 차수가 0인 새로운 이항 트리를 생성하고 이 트리를 이항 힙에 병합시켜 수행합니다.

힙에 차수가 0인 이항트리가 없다면 루트 노드에 새로 연결하게 되면 삽입이 끝입니다. 위 상황처럼 0 차수 노드가 힙에 있다면 이항 힙의 조건 중 차수 별로 0개 혹은 1개의 트리만 가질 수 있으므로 두 이항 트리를 합병하게 되고 결과로 차수가 1인 이항 트리가 생성됩니다.

이러한 과정을 반복하여 이항 힙의 조건이 만족할 때 까지 반복을 합니다.

삽입 결과

0~n까지 모든 차수의 이항트리가 힙에 있을 경우 총 n+1번의 병합이 이루어지게 되며 병합 과정에 의하여 소요시간은 O(log n)만큼의 시간이 소요됩니다.

 

삭제

힙에서 삭제는 가장 가중치가 높은 노드를 삭제하는 것을 의미합니다. 예를 들어 최소 이항 힙 에서의 삭제는 최솟값 삭제를 의미합니다. 과정이 조금 복잡하기 때문에 위키피디아의 그림을 빌려오겠습니다.

이항 힙 최솟값 삭제

a, b) 루트 노드들 중 최솟값을 찾고 해당되는 트리를 힙에서 분리합니다.

c) 분리한 이항 트리에서 루트를 삭제하고 나면 자식들 또한 이항 힙 구조로 되어 있습니다. 이 트리들을 기존 힙에 병합을 합니다.

* 이때 병합연산을 줄이기 위하여 저는 그림에서 처럼 차수가 적은 순으로 병합을 하지 않고 루트를 삭제하고 남은 n-1, n-2.. 2, 1 순서로 병합을 진행하였습니다. n차수의 트리를 병합하면 n+1의 트리가 생성되고 n-1 차수의 트리를 병합하면 n차수의 트리가 생성되기 때문에 차수가 높은 트리를 먼저 병합하게 되면 차수가 가장 높은 트리의 병합만 연쇄 병합을 하게 되고 나머지 차수의 트리의 병합 시 단 한 번의 병합이 이루어지게 되기 때문에 좀 더 효율적이라고 생각하여 이 방법을 사용하였습니다.

 

코드

#include <cstdio>
#include <queue>
using namespace std;
typedef struct node {
    int key;
    int degree;
    node *down,  *right;//child, sibling
    node(int key) : key(key), degree(0), down(NULL), right(NULL) {};
}node;
 
node *binomial_heap;
void merge_tree(node *a, node* b) {//merge tree a <- b
    node *prev = NULL;
    for (; a && a->degree < b->degree; prev = a, a = a->right);
    if (!a) {
        prev->right = b;
        b->right = NULL;
    }
    else if (a->degree != b->degree) {//insert middle or end
        if (prev)
            prev->right = b;
        b->right = a;
    }
    else {//merge
        b->right = a->right;
        while (b && a->degree == b->degree) {//Until a different order of node comes out
            if (a->key > b->key) {//b => top
                if (prev)
                    prev->right = b;
                else//front node
                    binomial_heap = b;
                b->degree++;
                a->right = b->down;
                b->down = a;
                a = b;
                b = b->right;
            }
            else {//a => top
                a->degree++;
                a->right = b->right;
                b->right = a->down;
                a->down = b;
                b = a->right;
            }//insert node at front of children
        }
    }
}
 
void insert(int key){
    node *tmp_node = new node(key);
    if (!binomial_heap || binomial_heap->degree) {//empty root or doesn't have 0 degree
        tmp_node->right = binomial_heap;
        binomial_heap = tmp_node;
    }
    else {//merge in order starting with a binomial tree with zero degree
        
        merge_tree(binomial_heap, tmp_node);
    }
}
void pop() {
    if (!binomial_heap) {
        printf("heap is empty\n");
        return;
    }
    node *cur = binomial_heap, *min = binomial_heap, *prev = NULL, *min_prev = NULL;
    while (cur) {//find min root
        if (min->key > cur->key) {
            min = cur;
            min_prev = prev;
        }
        prev = cur;
        cur = cur->right;
    }
    if (min_prev)
        min_prev->right = min->right;
    else//front node
        binomial_heap = min->right;
    
 
    cur = min->down;
    delete min;//delete root
    while (cur) {//merge heap and children
        prev = cur;
        cur = cur->right;
        if (!binomial_heap || binomial_heap->degree) {//empty root or doesn't have 0 degree
            prev->right = binomial_heap;
            binomial_heap = prev;
        }
        else {//merge in order starting with a binomial tree with zero degree
            merge_tree(binomial_heap, prev);
        }
    }
}
void print() {//level order
    node* cur = binomial_heap;
    queue<node*> que;
    while (cur) {
        printf("degree %d :\n%d\n", cur->degree, cur->key);
        que.push(cur->down);
        while (!que.empty()) {
            node* tmp = que.front();
            que.pop();
            while (tmp) {
                printf("%d ", tmp->key);
                que.push(tmp->down);
                tmp = tmp->right;
            }
        }
        printf("\n");
        cur = cur->right;
    }
}
int main() {
    int t;
    while (1) {
        printf("1: insert\n2: pop(min)\n3: print level order\n4: exit\noperation : ");
        scanf("%d", &t);
        switch (t) {
        case 1:
            printf("key : ");
            scanf("%d", &t);
            insert(t); 
            break;
        case 2:
            pop();
            break;
        case 3:
            print();
            break;
        case 4:
            return 1;
        }
        putc('\n', stdout);
    }
    
}