이항 힙
이항 힙에 대해 설명한다.
이항힙
[편집]컴퓨터 과학 분야에서는 이항힙(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인 이항 트리이다.
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 인 세 개의 이항 트리로 구성된다 (아래의 그림 참조).
구현
[편집]이항 트리의 루트 노드에 임의 접근(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)에서 무한대 값을 뺀다. (여기서 무한대 값을 뺀다는 의미는 이 제거하려는 구성요소의 키를, 힙에 포함된 어떠한 구성요소의 키보다 더 작게 만든다는 의미이다) 그리고서 힙에서 최소값 삭제 연산을 수행한다.
수행시간
[편집]다음의 시간 복잡도는 Binary Heap, Binomial Heap, Fibonacci Heap에 대해서만 나타난 것이다.
| Binary heap | Binomial heap | Fibonacci heap | |
|---|---|---|---|
| MAKE-HEAP | Θ(1) | Θ(1) | Θ(1) |
| INSERT | Θ(lg n) | O(lg n) | Θ(1) |
| MINIMUM | Θ(1) | O(lg n) | Θ(1) |
| EXTRACT-MIN | Θ(lg n) | Θ(lg n) | O(lg n) |
| UNION | Θ(n) | O(lg n) | Θ(1) |
| DECREASE-KEY | Θ(lg n) | Θ(lg n) | Θ(1) |
| DELETE | Θ(lg n) | Θ(lg n) | O(lg n) |
참고 문헌
[편집]- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 19: Binomial Heaps, pp. 455–475.
- Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309–314.