168. Merge Sort Tree

이전에 병합 정렬이라는 정렬 방법을 소개한 적이 있다. 이걸 응용해서 자료구조로 써먹는 방법을 알아본다.

 

머지 소트 트리(Merge Sort Tree)^[각주:1]는 병합 정렬 과정을 세그먼트 트리에 저장한 자료 구조이다. 앞서 병합 정렬의 시간복잡도와 공간복잡도가 $\Theta(n \lg n)$이라고 했는데, 정렬 과정에서 생긴 데이터를 버리지 않고 그대로 저장하면 머지 소트 트리를 만들 수 있다. 즉 $\Theta(n \lg n)$의 시간복잡도로 $\Theta(n \lg n)$의 메모리를 사용하는 머지 소트 트리를 만들 수 있다.

 

$$[6, 3, 5, 7, 1, 4, 2]$$

이 수열로 머지 소트 트리를 만들어 보자. 구간을 분할하는 부분은 별로 중요하지 않기 때문에 합치고 정렬하는 부분만 트리로 만들면 된다.

트리의 각 노드에 단일 원소 대신 리스트가 저장된다는 점이 세그먼트 트리와의 차이점이다. 또한 원소의 개수가 $2$의 거듭제곱이 아니라서 트리가 완전 이진 트리가 아니지만 수열 뒤에 $\infty$를 적당히 추가해서 완전 이진 트리를 만들 수도 있다. $\infty$는 정렬 과정에 별다른 영향을 주지 않기 때문에 구현하기 편한 것을 쓰면 된다.

여기서 간선을 다 생략하고 표처럼 보이게 하면 이렇게 된다.

아래에서 $k$번째 줄이 $2^{k - 1}$개의 원소로 이루어진 리스트가 이어진 구조로 되어 있는 것을 알 수 있다. 실제로 구현할 때에도 이와 비슷한 구조로 메모리에 저장할 것이다.

 

구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
int a[18][132000];
int main()
{
    int n;
    for(int i = 1; i <= n; i++)cin >> a[0][i];
    for(int i = n + 1; i <= 1 << 17; i++)a[0][i] = 1 << 30;
    for(int k = 1; k <= 17; k++)
    {
        for(int p = 1; p <= 1 << 17; p += 1 << k)
        {
            for(int i = 0, j = 0; i < 1 << k - 1 || j < 1 << k - 1;)
            {
                if(j == 1 << k - 1 || i < 1 << k - 1 && a[k - 1][p + i] < a[k - 1][p + (1 << k - 1) + j])
                {
                    a[k][p + i + j] = a[k - 1][p + i];
                    i++;
                }
                else
                {
                    a[k][p + i + j] = a[k - 1][p + (1 << k - 1) + j];
                    j++;
                }
            }
        }
    }
}

이 코드에서는 트리의 높이를 고정했는데, 원소의 개수에 따라 가변적으로 정할 수도 있다. 부모 노드의 리스트를 채우는 작업은 양쪽 자식 노드의 리스트를 합치고 정렬하는 것과 같고, 양쪽 자식 노드의 리스트가 모두 정렬된 상태이므로 결국 정렬된 두 리스트를 합치는 것이 된다. 이건 나중에 설명할 투 포인터를 이용해서 선형 시간에 할 수 있고, 위의 코드도 이 방법을 사용했다.

그렇다면 이걸 어디에 쓸 수 있는지 연습문제를 통해 알아보기로 한다.

 

[연습문제]

 

BOJ 13544. 수열과 쿼리 3 (Platinum III)

위의 구현 예시에는 각각의 노드에 대응하는 구간을 저장하는 부분이 생략되었지만 세그먼트 트리와 비슷한 방식으로 노드마다 대응하는 구간을 구할 수 있고, 세그먼트 트리와 비슷하게 탐색을 진행하면서 구간 $[i, j]$에 포함되는 노드마다 이분 탐색으로 $k$보다 큰 원소의 개수를 세서 다 더하면 된다. 쿼리마다 최대 $\lg N$개의 노드에서 이분 탐색을 진행하므로 $O(M \lg^2 N)$의 시간복잡도로 전체 문제를 해결할 수 있다.

 

BOJ 7469. K번째 수 (Platinum II)

13544번의 풀이에 매개변수 탐색을 추가한다. 어떤 수 $x$가 구간 $[i, j]$에서 몇 번째로 작은지를 확인하면서 $k$번째로 작은 값이 되는 최소의 $x$를 찾는 것이다.

 

CF 1404C. Fixed Point Removal (2300)

(Todo)

 

→ solved.ac tag: merge_sort_tree

---

1. 이니셜은 MST가 되는데 이게 최소 스패닝 트리의 이니셜과 겹치기 때문에 머지 소트 트리의 이니셜로 이걸 쓰는 빈도는 높지 않다. [본문으로]