이항 힙

이항 힙에 대해 설명한다.

구현

이항 트리의 루트 노드에 임의 접근(random access)을 필요로 하는 연산이 없기 때문에, 이항 트리의 루트 노드들은 연결 리스트(linked list)에 저장할 수 있다. 이때 트리의 증가 순으로 저장된다.

병합

function mergeTree(p, q)
if p.root.key <= q.root.key
return p.addSubTree(q)
else
return q.addSubTree(p)
앞서 언급하였듯이, 가장 단순하고도 중요한 연산은 이항 힙 내에서 order가 동일한 두 개의 이항 트리를 병합(merge)하는 것이다. 이항 트리의 구조 때문에, 이들 두 이항 트리는 쉽게 merge될 수 있다. 이항 트리 내에서 루트 노드는 가장 작은 구성요소이므로, 두 개의 키를 비교하여 둘 중 더 작은 것을 찾으면 그것이 최소 키이며, 이것이 새로운 루트 노드가 되는 것이다. 그리고서 나머지 트리는 결합된 트리의 하위 트리가 된다. 이 연산이 바로, 두 개의 이항 힙에 대한 완전한 병합의 기초가 된다.
두 힙을 merging하는 연산은 아마도 가장 흥미로우며, 대부분의 다른 연산에서도 서브루틴(subroutine) 으로 쓸 수 있다. 두 힙의 루트 리스트(list)는 동시에 순회(traverse)할 수 있는데, merge 알고리즘에서와 유사한 방법으로 한다.
만일 두 힙 중 오직 하나의 힙이 order j인 트리를 포함한다면, 이 트리는 병합(merge)된 힙으로 이동하게 된다. 만일 두 힙 모두order j인 트리를 포함한다면, 두 트리는 하나의 트리로 merge되어order j+1인 트리가 된다. 이렇게 하여 최소-힙 특성을 다시 만족하게 된다. 이때, 힙 내에 존재하는order j+1인 어떤 다른 트리와 이 트리를 merge해야 할 경우가 나중에 있을 수도 있음을 기억하자. 알고리즘을 수행하는 동안, 임의의 order를 가진 트리를 최대 세 개까지 조사해야 한다. (두 개는 우리가 merge할 두 개의 힙에서, 나머지 하나는 더 작은 두 트리에서 발생한다).
이항 힙 내의 각각의 이항 트리가, 힙의 크기를 이진수로 표현한 수의 각 비트에 해당되기 때문에, 두 힙을 병합하는 것과 두 힙의 크기(size)를 이진수로 합한 것(우측에서 좌측으로 합산) 사이에는 유사성이 존재한다. 덧셈을 하는 동안 자리 올림(carry)이 발생할 때마다, 이것은 merge 과정 중 두개의 이항 트리가 merge되는 것에 해당한다.
각 트리의 order는 최대log n이고 따라서 실행 시간은 O(log n)이다.
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)
이에 해당하는 상세한 그림은 아래와 같다.

키 감소

구성요소의 키(key)를 감소(decreasing)한 후에는, 이 구성요소의 키가 자신 부모의 키보다 작아질 수 있다. 이렇게 되면 최소-힙 특성(minimum-heap property)을 위반하게 된다. 이러한 일이 생기면, 이 구성요소를 부모와 서로 맞바꾼다. 이러한 맞교환은 부모의 부모에서 다시 일어날 수도 있다. 이러한 맞교환을 이 힙이 최소-힙 특성을 위반하지 않을 때까지 상위로 올라가면 반복한다. 각 이항 트리는 최대 log n의 높이(height)를 가지며, 따라서 이에 걸리는 시간은 O(log n)이다. 키감소에 대한 내용을 구체화 시킨 그림은 아래와 같다.

제거

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