#4 알고리즘 Advanced Data Structure : Binomial Heap

Binomial Heap을 배우기 위해서 Binomial Tree가 어떤 것인지 부터 알아보겠습니다. 

Binomial Tree

  Binomial Tree는 우선순위 큐 형태의 자료구조입니다. 아래 그림과 같이 한 Tree의 루트 노드가 다른 루트 노드를 가리키는 형태입니다. 

  노드의 수는 2^k(루트에 새로 붙여지는 트리와 붙는 트리의 크기가 같다), 루트에 붇기 때문에 높이는 1씩 증가하게되며 트리의 깊이는 K combination i(K에서 i를 뽑는 경우의수), 그리고 루트의 degree가 가장 크게 됩니다. 

Binomial Heap

  Binomial Heap의 각각의 Binomial Tree는 min-heap입니다. 그리고 k값이 같은 Binomial Tree는 존재하지 않습니다(차수가 같은 트리가 존재하지 않는다는 뜻). 아래 그림과 같이 루트가 연결되어있으며 연결된 루트는 sibling노드에 의해 연결되어 있습니다. 

Binomial Heap의 용도

  Binomial Heap은 힙을 합칠때 사용합니다. Binomial Heap의 정의 중 차수가 같은 Binomial Tree가 존재하지 않는다 라는 것이 있었습니다. 차수가 같은 Binomial Tree가 존재하지 않는다는 뜻은 존재한다 존재하지 않는다로 나타냈을때 이진수 형태로 나타낼수 있다는 것입니다. 예를들어 1차 Tree가 존재하고 2차 트리가 존재하고 3차 트리가 존재하지 않는다면 이 Binomial Heap은 110로 나타낼수 있습니다. 그리고, 만약 111과 같은 형태의 Binomial Heap과의 덧셈을 한다면, 이진수의 덧셈으로 힙의 덧셈 과정을 간략화 할 수 있습니다. 

  두 트리가 합쳐질때는 루트의 크기가 작은쪽에 큰 쪽이 붙게 됩니다. 

Binomial Heap의 큰 이점

  바로 Heap의 덧셈을 Heap자료구조의 연산이 거의 그대로 적용 가능한 형태로 상수시간내애 수행할 수 있다는 점입니다. 구현도 매우 간단합니다. 예를들어 미국행 비행기 출발시간이 들어있는 우선순위큐가 있고, 프랑스행 비행기 출발시간이 들어있는 우선순위큐가 있을때 둘을 합쳐서 이륙 순서대로 정렬하고싶다면, 그리고 이와같은 연산이 빈번하게 발생하는 시스템이라면 Binomial Heap과 같은 자료구조가 큰 위력을 발휘 할 수 있습니다. 내용이 간단한만큼 구현도 쉽고, 간단한 아이디어로 큰 속도 향상을 얻을 수 있는 자료구조기반의 알고리즘입니다.