이항 힙

**이항 힙**에 대해 설명한다.

## 이항힙
컴퓨터 과학 분야에서는 이항힙(binomial heap)은 이진힙(binary heap)과 유사하지만, 이항힙(binomial heap)이 서로 다른 두개의 힙(heap)을 병합(merge)하는데 더 빠르다. 이는 특별한 트리구조에 의해서 구현된다. 이 트리구조에 대한 설명은 뒤에서 더 자세히 설명하도록 하겠다.

이항 힙(binomial heap)은 이항 트리(binomial tree)를 결합하여 구현하는데, (이것은 이진 힙(binary heap)과 비교되는데, 이진 힙은 단일 이진 트리 모양을 하고 있다) 다음과 같이 재귀적 방법으로 이항 트리를 정의한다.
* Order가 0인 이항 트리는 단일 노드이다.
* Order가 k인 이항 트리는 루트 노드를 가지는데 이 루트 노드의 자식은, order가 (이 순서로) k−1, k−2, ..., 2, 1, 0인 이항 트리이다.

500px|섬네일|가운데|Order가 0부터 3인 이항 트리: 각 트리는 루트 노드와 하위 트리(subtree)로 구성되는데, 이때 하위 트리는 자신보다 order가 낮은 모든 이항 트리가 하위 트리가 된다. 그림에서 강조하여 표현된 것이 하위 트리들이다. 예를 들어, order가 3인 이항 트리는 order가 2, 1, 0 인 이항 트리(각각 파란색, 녹색, 붉은색으로 표시함)와 연결되어 있다.

Order가 k인 이항 트리는2k개의 노드를 가졌으며, 트리의 높이는 k이다.
이러한 특이한 구조 때문에, order가 k인 이항 트리는 order가 k-1인 두 개의 트리를 가지고 쉽게 구성할 수 있다. 즉, 하나의 트리(order가 k-1인 트리)의 루트 노드의 가장 왼쪽에, 나머지 하나의 트리(order가 k-1인 또다른 트리)를 자식 노드로 붙이면 간단히 만들어진다. 이러한 특성은 이항 힙 merge 연산의 중심 개념이 되는데, 다른 일반 힙에 비해 이항 힙이 가진 주요한 장점이라 하겠다.
이름은 모양에서 비롯되었다: order가 n인 이항 트리는 깊이(depth) d에서 (n¦d)의 노드를 가진다. (이항 계수 참조)

## 구조
이항 힙은 다음과 같은 이항 힙의 특징을 만족시키는 이항 트리의 집합으로 구현된다:
* 힙을 구성하는 각 이항 트리는 최소-힙 특성(minimum-heap property)을 따른다: 노드의 키(key)는 자신의 부모 노드의 키(key) 값보다 크거나 같다.
* 0 order를 포함하여 각 order별로 1개 또는 0개의 이항 트리가 있을 수 있다.
첫번째 특성은 각 이항 트리의 루트가 트리에서 가장 작은 키를 포함할 것을 보장하는 것으로, 이러한 특성은 전체 힙에 적용된다.
두번째 특성은 n개의 노드를 가지는 이항 힙은 많아야 log n + 1의 이항 트리로 구성된다는 것을 의미한다. 사실상, 이러한 트리의 수와 order는 노드 수인 n에 의해 유일하게 결정된다. 즉 각 이항 트리는 n이라는 수를 이진수로 나타냈을 때 그 각각의 수(digit)에 해당한다. 예를 들어, n이 13이라면, 13을 이진수로 표현한 것은 1101이다. 따라서 13개의 노드를 가진 이항 힙은 order가 3,2,0 인 세 개의 이항 트리로 구성된다 (아래의 그림 참조).

500px|섬네일|가운데|서로 다른 키를 가진 13개의 노드로 구성된 이항 힙의 예
힙은 Order가 0, 2, 3인 세 개의 이항 트리로 구성된다.

## 구현
이항 트리의 루트 노드에 임의 접근(random access)을 필요로 하는 연산이 없기 때문에, 이항 트리의 루트 노드들은 연결 리스트(linked list)에 저장할 수 있다. 이때 트리의 증가 순으로 저장된다.
500px|섬네일|가운데|위의 그림을 이용하여 아래의 병합(merge), 삽입(inserting), 최솟값 찾기(find minimum), 삭제 (delete), 키 감소(decrease key) 등을 설명할 수 있다.

## 병합
200px|섬네일|오른쪽|Order가 동일한 두 개의 이항 트리를 병합하려면, 우선 루트의 키(key)를 비교한다. 7>3이므로, 좌측의 검은색으로 표시한 트리(루트 노드가 7인 트리)가 우측의 회색 표시된 트리(루트 노드가 3인 트리)에 하위 트리로 결합된다. 그 결과 order가 3인 트리가 생겼다.

function mergeTree(p, q)
 if p.root.key 

function merge(p, q)
 while not (p.end() and q.end())
 tree = mergeTree(p.currentTree(), q.currentTree())

 if not heap.currentTree().empty()
 tree = mergeTree(tree, heap.currentTree())

 heap.addTree(tree)
 heap.next(); p.next(); q.next()

## 삽입
새로운 구성요소를 힙에 삽입(inserting)하는 연산은, 이 삽입하려는 구성요소를 포함한 힙을 새로 생성한 후, 이 힙을 기존의 힙에 merge함으로써 간단히 수행할 수 있다. Merge 연산 때문에O(log n)만큼의 시간이 소요된다. 그러나, 일련의 삽입연산을 연속적으로 n 번 수행하는 경우 삽입은 O(1)의 분할상환 시간을 가지게 된다. (O(1)이라 함은 상수만큼의 시간이 걸린다는 의미). 삽입의 절차는 아래와 같이 나타낼 수 있으며, 이는 위의 그림 (a), (b)를 보면서 degree, child, sibling 및 head의 개념을 알면 이해하기 쉬울 것이라 판단 된다.
1 H' MAKE-BINOMIAL-HEAP()
2 p[x] NIL
3 child[x] NIL
4 sibling[x] NIL
5 degree[x] 0
6 head[H'] x
7 H BINOMIAL-HEAP-UNION(H,H')

## 최솟값 찾기
힙에서 최솟값(minimum)을 찾기 위해서는, 이항 트리(binomial tree)의 루트들 중에서 최솟값을 찾아야 한다. 이것은O(log n)의 시간 안에 쉽게 수행될 수 있는데, 왜냐하면 힙 안에는 단지O(log n) 개의 트리가 존재하고 따라서 조사해야 할 루트의 개수 또한O(log n) 이기 때문이다.
최솟값 구성요소를 포함하고 있는 이항 트리를 가리키는 포인터를 사용함으로써, 이 연산에 걸리는 시간을 O(1)으로 줄일 수 있다. Find minimum(최솟값을 찾는) 연산 외의 다른 연산을 수행할 때에는 반드시 이 포인터를 업데이트해야 한다. 어떠한 연산에 대해서도 실행시간을 증가시키지 않고 이것을 O(log n) 시간 안에 수행할 수 있다.

## 최솟값 제거
힙에서 최솟값을 가지는 구성요소를 삭제(delete the minimum element) 하려면, 먼저 해당 구성요소를 찾고, 이 구성요소가 들어 있는 이항 트리에서 이 구성요소를 삭제한 후, 이것의 하위트리 리스트를 구해야 한다. 그리고 나서 이 하위트리 리스트를 이항 힙으로 변환하여야 하는데, 이것은 가장 작은 것부터 가장 큰 것 순으로 순서를 재배치하여 수행한다. 그리고서 이 힙을 기존의 힙에 merge한다. 이 트리는, 많아야 log n개의 자식을 가지기 때문에, 새로운 힙을 생성하는데 걸리는 시간은O(log n)이다. 또한 힙을 merge하는데 O(log n)의 시간이 걸리므로, 최솟값 삭제 연산 전체에 걸리는 시간은O(log n)이다. 

function deleteMin(heap)
 min = heap.trees().first()
 for each current in heap.trees()
 if current.root < min.root then min = current
 for each tree in min.subTrees()
 tmp.addTree(tree)
 heap.removeTree(min)
 merge(heap, tmp)

이에 해당하는 상세한 그림은 아래와 같다.
500px|섬네일|가운데

## 키 감소
구성요소의 키(key)를 감소(decreasing)한 후에는, 이 구성요소의 키가 자신 부모의 키보다 작아질 수 있다. 이렇게 되면 최소-힙 특성(minimum-heap property)을 위반하게 된다. 이러한 일이 생기면, 이 구성요소를 부모와 서로 맞바꾼다. 이러한 맞교환은 부모의 부모에서 다시 일어날 수도 있다. 이러한 맞교환을 이 힙이 최소-힙 특성을 위반하지 않을 때까지 상위로 올라가면 반복한다. 각 이항 트리는 최대 log n의 높이(height)를 가지며, 따라서 이에 걸리는 시간은 O(log n)이다. 키감소에 대한 내용을 구체화 시킨 그림은 아래와 같다.
500px|섬네일|가운데|(a)의 y에 해당하는 내용은 7로 감소시키면, 이는 parent키의 16보다 작으므로 (b)의 과정과 같이 7과 16의 노드가 교환되게 된다. 그리고 이 값은 parent 키의 10보다 작으므로 (c)의 과정과 같이 노드가 한번더 교환하게 되며 결론적으로 (c)의 결과값과 같이 나타나게 된다.

## 제거
힙에서 구성요소를 제거(delete)하려면, 이 제거하려는 구성요소의 키(key)에서 무한대 값을 뺀다. (여기서 무한대 값을 뺀다는 의미는 이 제거하려는 구성요소의 키를, 힙에 포함된 어떠한 구성요소의 키보다 더 작게 만든다는 의미이다) 그리고서 힙에서 최솟값 삭제 연산을 수행한다.

## 수행시간
다음의 시간 복잡도는 Binary Heap, Binomial Heap, Fibonacci Heap에 대해서만 나타난 것이다.

## 참고 문헌
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 19: Binomial Heaps, pp. 455–475.
* Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309–314.

분류:힙 (자료 구조)
분류:힙