HeapSort

HeapSort에 대해 알아보려고 한다.

HeapSort는 Binary Heap 자료 구조를 기반으로 Selection Sort와 거의 비슷하다. 

잠깐, 본격적으로 알아보기 전에 Binary Heap에 대해 먼저 알아보자.

Binary Heap은 완전한 Binary Tree (마지막 노드를 제외하고 각 Level에 노드가 가득찬 것 - 거의 완전하게 노드로 가득찬 Tree)이다. 

그림 1. Complete Binary Tree

위의 그림처럼 구성되는데 일반 Binary Tree와는 다르게 Binary Heap은 부모 노드를 2가지 방식으로 채운다. 하나는 두 자식 노드 보다 값이 클 때이고 다른 하나는 두 자식 노드 보다 값이 작을 때이다. (각각 max heap, min heap)

이처럼 Heap Sorting은 Binary Heap 구조를 기반으로 한다.

그럼 본격적으로 Heap Sort에 대해 알아보겠다.

보통 Heap Sort 관련해서 대부분 배열을 사용하여 Heap Sort를 구성한다. 물론 다른 자료 구조를 사용하여 Heap Sort를 구성하여도 상관없지만 배열을 사용하는 것이 일단 쉽고 직관적이기 때문이다. 또한 추가적인 메모리 사용 측면에서 효율적이기도 하다. (메모리는 배열의 특징으로 봐도 무방할 것 같다.)

한 가지 예로 배열의 인덱스를 사용하면 부모 및 자식 노드를 쉽게 찾을 수 있다.

- Parnet Node : i 

- Child Node(Left) : 2*i + 1

- Child Node(Right) : 2*i + 2

* 참고 : 인덱스가 0으로 시작한다고 할 때 노드를 찾는 방식이다.

관련 코드를 먼저 살펴보자.

def heapify(arr, n, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < n and arr[i] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < n and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, n, largest) # The main function to sort an array of given size def heapSort(arr): n = len(arr) # Build a maxheap. for i in range(n, -1, -1): heapify(arr, n, i) # print(arr) # One by one extract elements for i in range(n - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0)

코드를 보고 한번에 이해가 되면 좋겠지만 그렇지 않으면 설명을 바탕으로 이해해보자.

실제 정렬하는 방법은 heap 원리를 조금 응용한다. 내부 알고리즘 동작 순서를 하나씩 따라가 보면 아래와 같이 3 단계로 이루어진다.

1) 배열에 존재하는 모든 값을 root 노드부터 (인덱스 0) 마지막 노드까지 heapify 한다. 

2) root 노드를 가장 마지막 노드와 swap 한다.

3) 마지막 노드를 제외하고 heapify 한다.

(오름차순 정렬일 경우)

여기서 1 단계는 전체 배열을 heapify 하는데, heap 구성 방식 처럼 부모 노드 값이 자식 노드보다 크게 만들기 위함이다. 그런데 단순 heap tree은 인덱스 순서대로 값이 정렬되어 있다고 보장할 수 없다. 다만 자식 노드보다는 큰 노드만 알 수 있다.

때문에 루트 노드를 사용한다. 즉, max heap일 경우는 항상 부모 노드는 자식 노드보다 값이 크다. (결국 루트 노드는 가장 값이 크다) 루트 노드를 heap 삭제처럼 마지막 노드 값과 swap 하여 배열의 가장 마지막 자리에 넣는다. 그리고 마지막 노드를 제외하고 동일한 방식으로 계속 돌린다.

결과적으로 배열은 가장 큰 값부터 작은 값까지 순차적으로 정렬이 된다. (물론, max heap을 사용하는 방식은 오름차순 정렬일 때이다.)

이 같은 내용을 바탕으로 다시 코드를 확인해보면,

heapify은 특정 인덱스로 부터 max heap을 유지하기 위해 recursive 하게 동작한다. 그래서 처음 for-loop에서는 max heap 배열을 구성한 이후, 두 번째 for-loop에서 최상단 값을 하나씩 하나씩 뽑아낸다.

Heap sort의 시간 복잡도는 O(nLogn)이다. 그 즉슨, heapify가 binary tree로써 O(Logn)이고 처음 heap tree를 만들때 모든 노드에 돌리기 때문에 n을 사용한다.

결과적으로 O(nLogn)이 된다.

다만, 공간 복잡도는 O(1)으로 추가 메모리를 사용하지 않고 기존 배열 메모리만 가지고 정렬하기 때문이다.

Reference

- https://www.geeksforgeeks.org/heap-sort/