[Algorithm] Heap Sort (힙 정렬)

0. Heap Sort란?

 

자료구조인 heap을 이용한 정렬이다. 먼저 heap이 무엇인지 살펴보자.

 

1) Heap

 

heap은 max-heap, min-heap 두 개로 나눌 수 있다. max-heap을 이해하면 min-heap을 이해하기 쉬우니 max-heap을 살펴보자.

heap은 이진 트리의 형태를 띈다. 이진 트리란, 트리 구조를 가지고 있으면서 각 노드가 최대 2개의 자식을 갖는 트리이다.

 

max-heap이란, 부모의 값이 자식의 값보다 항상 큰 이진 트리이다. 따라서 루트 노드는 전체의 최댓값을 갖게 된다.

min-heap은 부모의 값이 자식의 값보다 항상 작은 이진 트리이다. 따라서 루트 노드는 전체의 최솟값을 갖게 된다.

 

2) 이진 트리를 배열으로 구현하기

 

이진 트리 형태를 떠올리면 배열과는 거리가 있다고 느껴질 것이다. 그러나 이를 배열로 구현할 수 있다. 다음 그림을 살펴보자.

 

이진 트리를 배열로 나타내기 위한 과정

다음과 같은 이진 트리(max-heap 구조를 띈다)에서, 부모 노드를 0으로 하면 자식 노드인 7과 8을 각각 1, 2번이라고 하자. 이는 그림에서와 같이 부모 노드에 2를 곱한 다음 1, 2를 각각 더하면 구할 수 있다. 다른 노드들도 마찬가지인 것을 그림을 통해 볼 수 있다.

따라서 위와 같은 이진 트리는 [9, 7, 8, 4, 3, 5, 6]으로 바꿀 수 있다.

 

3) Heap Sort (힙 정렬) - max-heap을 이용하여

 

max-heap은 원소들 중 최댓값을 루트 노드로 갖는다. 따라서 max-heap을 만드는 과정을 n개, n-1개, ..., 1개에 대해 반복하면 정렬할 수 있을 것이다. 최대를 찾아 계속 뒤로 보내주기만 하면 되기 때문이다.

하나의 heap을 만드는데는 log(n)의 시간이 소요된다. 이를 n개의 원소에 대해 반복하므로 시간복잡도는 O(nlogn)이 된다.

 

3)-A. how to make a max-heap?

 

max-heap을 만든다는 게 말이 쉽지 배열에서는 어떻게 구현하냐는 생각을 할 것이다. 

위의 예제에서 최대인 9를 맨 뒤로 보내면서 6과 바꾸면, max-heap의 구조가 깨지게 된다.

따라서 다시 이를 max-heap으로 만들어주어야 하고, 이를 heapify라고 부를 것이다. (min-heap의 경우에도 똑같이 부른다)

좀 더 자세히 말하자면, 현재 노드를 기준으로 이 노드가 heap 특성에 맞을 때가지 계속 밑으로 내려주는 과정을 말한다. 

 

아래와 같은 그림에 대해 heapify를 한 번 진행한다고 하자.

 

초기 이진 트리

배열로 나타내면 [5, 3, 6, 4, 7, 8, 9]가 될 것이다. 현재 노드는 n/2번째로 잡는다. 가운데부터 첫번째까지 heapify 과정을 수행해주는 것이다. 단, heapify는 시작한 노드에서 자식이 없는 노드여서 종료될 때까지 재귀적으로 수행되기 때문에, n/2번째 노드에서 시작함으로써 모든 노드에 대해 heapify를 수행할 수 있게 된다. 여기서는 3번째 원소인 6이 될 것이다. 

 

max-heap의 특성인 '부모 노드가 자식 노드보다 크다'를 만족시켜주기 위해, 자식 노드를 검사해 가장 큰 노드를 찾는다. 이를 largest라고 하겠다. 여기서의 largest는 6번 노드, 즉 9가 될 것이다. 이제 현재 노드 (부모) 와 largest 노드 (가장 큰 자식) 을 교환한다.

첫 번째 교환이 일어난 후의 이진 트리. 아직 max-heap의 특성을 만족하지 못한다. 

다음과 같은 구조가 될 것이다. 재귀적인 구조이므로 largest에 대해 heapify를 진행해야 한다. 그러나 현재 largest인 6은 자식 노드가 없으므로 종료된다.

아까 3번째 원소에서 시작했으니 이제 2번째 원소에서 다시 heapify를 진행한다. 3에 대해 heapify를 진행하면, 다음과 같은 구조가 될 것이다.

 

2번째 원소에 대해 heapify를 진행한 결과

이제 첫번째 노드에 대한 heapify만 남았다. 

 

최종 max-heap

 

max-heap이 완성되었다. 배열로 구현하면 처음 제시한 트리에서 원소를 바꾸는 과정만 반복해주면 된다. 

 

3)-B. Heap Sort

 

이제 max-heap을 만드는 방법을 알았으니 이를 이용한 정렬을 할 수 있다. 0부터 n-1번까지 max-heap을 만들고, 다음엔 n-1번째까지, 이 과정을 반복하여 원소가 하나만 남을 때까지 heapify를 진행하고 맨 뒤로 루트를 보내준다 (실제로는 맨 뒤 원소와 교환한다). 그러나 맨 뒤 원소는 리프 노드이고, 이는 최댓값임을 당연히 보장할 수 없기 때문에 교환 후 heapify(0) 과정을 한번 더 거쳐줘야 한다. heapify(0)은 0번 노드부터 모든 자식 노드에 대해 heapify를 수행하기 때문에, 이렇게 하면 다시 max-heap을 만들 수 있다.

 

정리하자면 다음과 같다.

1. max-heap을 전체 배열에 대해 생성

2. 생성한 max-heap의 루트 노드와 맨 뒤 노드 교환

3. heapify(0)

4. 2, 3 정렬될 때까지 반복

 

2. 구현 

 

def swap(num, i, j):
    tmp = num[i]
    num[i] = num[j]
    num[j] = tmp

def heapify(num, root, n):
    left = 2 * root + 1
    right = 2 * root + 2
    max_idx = root
    if left < n and num[left] > num[max_idx]:
        max_idx = left
    if right < n and num[right] > num[max_idx]:
        max_idx = right

    if max_idx is not root:
        swap(num, root, max_idx)
        heapify(num, max_idx, n)

def heap_sort(num, n):
    mid = (n // 2) - 1
    for i in range(mid, -1, -1):
        heapify(num, i, n)

    for i in range(n-1, 0, -1):
        swap(num, 0, i)
        heapify(num, 0, i)

n = int(input())
nums = input()
num = nums.split()

for i in range(n):
    num[i] = (int)(num[i])

heap_sort(num, n)

for i in range(n):
    print(num[i], end=' ')

1) swap

python의 swap하는 방법을 잘 알고있다면 굳이 구현하지 않아도 된다. 바꾼다는 것을 강조하기 위해 구현했다. 

 

2) heapify

현재 노드인 root에 대해 오른쪽, 왼쪽과 비교하여 가장 큰 값을 찾는다. 바뀌었다면 (root가 max_idx가 아니라면) 교환을 수행하고, 교환이 수행된 자식 노드에 대해 다시 heapify를 진행한다.

 

3) heap-sort

 

첫 번째 포문에서 max-heap을 만들어주고, 두 번째 포문에서 만든 max-heap을 이용해 정렬을 진행한다. 두 번째 포문의 heapify(0)이 계속 max-heap을 유지할 수 있도록 해준다.