Github에 한글로 자료를 정리하고 있었는데 몇 가지 문제점을 느끼고 Tistory로 옮기는 것을 시도해보려 한다. 한글로 정리한 이유는 영어를 잘 못하는 한국 학생들을 위함이었는데, 생각해보니 영어와 친숙하지 않은 학생이 Github로 유입되길 기대하기는 힘들다고 판단된다.
---
이항 힙 (Binomial Heap)
아래 설명은 읽는 사람이 트리 이론 기초와 이진 힙(Binary Heap)을 이해하고 있다는 가정 하에 쓰여있다.
- 왜 이항 힙을 쓰는가?
이진 힙(Binary Heap)보다 삽입 연산이 더 빠른 것을 기대할 수 있다. 이진 힙이 삽입의 시간복잡도 O(logN)인데 비해 이항 힙은 시간복잡도 O(1)이다. 단, 이는 분할상환 시간복잡도(Amortized Time Complexity)를 고려한 것이고, 최악의 경우를 따진다면 이항 힙의 삽입 역시 O(logN)의 시간복잡도를 가진다. 분할상환 시간복잡도는 언젠가 따로 포스팅을 해야겠지만, 이항 힙의 분할상환 계산은 비교적 직관적으로 설명이 가능하여 삽입을 설명하는 부분에서 이해를 도울 것이다.
- 이항 힙, 이진 힙 형태 비교
이진 힙은 이진 트리이고, 트리 1개로 구성된다.
이항 힙은 어떤 노드의 자식이 3개 이상일 수 있고, 트리 여러 개로 구성된다. 즉 루트 노드가 여러 개일 수 있다.
이진 힙은 부모-자식 간의 값을 비교한다면, 이항 힙은 트리의 루트 노드 간의 값을 비교한다.
- 이항 힙의 형태
이항 힙은 여러 개의 트리로 구성된다고 앞서 말했는데, 이항 힙의 모든 트리는 노드의 개수가 2의 멱수이다. 그리고 모든 자연수는 2의 멱수의 합으로 나타낼 수 있다.
이항 힙에 20개의 데이터가 있다면 아래와 같이 이해할 수 있다.
* 16개의 노드를 가진 트리와 4개의 노드를 가진 트리, 총 2개의 트리로 구성된다.
* (20 = 16+4)
* 힙에서 1개의 데이터를 빼면, 노드 16개 트리, 노드 2개 트리, 노드 1개 트리, 총 3개의 트리로 구성된다.
* (20-1 = 19 = 16+2+1)
데이터가 N개라면 N을 이진수로 나타내어 보자. 이진수에서 1의 개수가 트리의 개수이고, 1이 표현하는 수가 해당 트리가 가진 노드의 개수이다.
이항 힙은 그 이름에 맞게 이항 계수와 연관이 있다. 잠시 파스칼의 삼각형을 보자.
1 = 1
2 = 1 + 1
4 = 1 + 2 + 1
8 = 1 + 3 + 3 + 1
16 = 1 + 4 + 6 + 4 + 1
오른쪽이 파스칼의 삼각형이고, 왼쪽은 각 줄을 모두 합한 수이며 이는 2의 거듭제곱 수(=멱수)이다.
최소 힙이라고 가정하고 아래 노드가 각각 2개인 트리 2개를 생각해보자.
> 3 - 4 (루트 노드 3, 자식 노드 4)
> 1 - 2 (루트 노드 1, 자식 노드 2)
2개 트리를 병합해보자.
- 트리의 병합
> 1 - 2
- 3 - 4 (루트 노드 1, 1의 자식 2와 3 그리고 3의 자식 4)
루트 노드 2개를 비교해서, 더 작은 값이 루트가 되도록 병합하였다.
또 다른 노드 4개인 트리가 있었다고 가정해보자.
> 5 - 6
- 7 - 8
트리 2개를 병합하면 아래와 같다.
> 1 - 2
- 3 - 4
- 5 - 6
- 7 - 8
이런 식으로 병합되는 트리는 힙의 조건을 만족한다. 이 경우 최소 힙이므로 모든 노드에 대해 부모 노드가 자식 노드보다 값이 작은 것을 알 수 있다.
트리의 레벨에 따른 노드 개수는 이항 계수를 따른다. 예제의 경우 노드가 8개이면 파스칼의 삼각형 4번째 줄에 해당한다. 루트 노드를 레벨 0으로 두었을때
* 레벨 0 노드 수: 1
* 레벨 1 노드 수: 3
* 레벨 2 노드 수: 3
* 레벨 3 노드 수: 1
2개의 힙 트리를 병합하는 작업의 시간복잡도는 O(1)이다.
- 이항 힙의 삽입
트리의 병합에 대해 배웠으므로, 이제 이항 힙을 구성할 수 있다.
데이터가 7개인 이항 힙이 있다면 트리 3개로 구성될 것이다. 앞으로 이항 힙의 트리들을 포레스트라고 부르겠다. 이를 이진수로 표현하면 111 이다. 여기에 데이터 1개를 추가하면 이진수에 값을 1 더하는 것만으로도 포레스트의 형태가 어떻게 변하는지 정확하게 알 수 있다.
> 111 + 1 = 1000
이항 힙에 대해 공부할 정도라면 눈치챘으리라 예상한다. LSB를 포함해 연속된 1의 개수만큼 트리의 병합이 발생한다. 데이터 개수가 7(111)이었으면 트리의 병합은 3번 일어나고, 6(110)이었으면 트리 간의 병합은 일어나지 않는다.
데이터 개수가 N이라면 연속된 1의 최대 개수는 logN 근방임을 알 수 있으며 삽입의 시간복잡도가 O(logN)임을 짐작할 수 있다. 그런데 글 처음에 언급했듯 이항 힙은 이진 힙보다 삽입 연산이 빠른 것을 기대할 수 있다. 데이터 8개를 연속으로 삽입하는 상황을 생각해보자.
- 0000 : 0
- 0001 : 1
- 0010 : 0
- 0011 : 2
- 0100 : 0
- 0101 : 1
- 0110 : 0
- 0111 : 3
- 1000
콜론 오른쪽의 숫자는 트리 병합이 발생하는 횟수를 적은 것이다. 트리 병합이 발생하는 횟수를 모두 합쳐보면 7이다. 8개를 삽입하는 과정 중 절반이 트리 병합을 한 번도 필요로 하지 않는다. 간단히 계산해보면 삽입을 N번 수행하는데 시간복잡도가 O(N)임을 유추할 수 있고, 이를 근거로 삽입 1회에 걸리는 시간복잡도를 O(1)이라 하는 대신 분할상환(Amotized)이라는 조건이 붙는 것이다. 이는 어디까지나 총계를 근거로 산정한 것이며, 최악의 경우 logN에 비례하는 연산이 일어난다는 사실은 변하지 않는다. 분할상환 시간복잡도의 계산/증명은 필자도 엄밀히 알지는 못하여 당장 상세한 설명은 어려움을 양해바란다.
- 이항 힙의 최솟값 찾기
포레스트의 루트 노드를 전부 비교해보면 된다. 이렇게 되면 시간복잡도가 O(logN)인데, 트리의 삽입 과정에서 병합할 때 미리 최솟값을 기억해두면 O(1)에 최솟값을 알 수 있다.
- 이항 힙의 최솟값 제거
포레스트 중에서 최솟값을 가진 트리를 생각해보자. 위의 예에서 가져와보면
> 1 - 2
- 3 - 4
- 5 - 6
- 7 - 8
인데, 최솟값인 1을 제외한 서브 트리들이 이항 힙의 포레스트가 될 수 있음이 보이는가?
> 2
> 3 - 4
> 5 - 6
- 7 - 8
이렇게 나온 3개의 트리를 기존 이진 힙 포레스트에 병합시키면 된다. 트리 병합을 최소로 하는 병합 순서를 생각해보고, 이에 관한 시간복잡도 계산은 각자의 몫으로 남겨두려 한다.
---
이해가 잘 가지 않는 부분 혹은 오류, 누락이 있다면 댓글이나 이메일(jjgjoojis@gmail.com)로 알려주시면 도움이 될 수 있도록 글을 보충하겠습니다.
본문과 별도로 국문 자료를 찾기 힘든 자료구조 및 알고리즘에 대한 설명을 요청해주셔도 좋습니다.
