[Algorithm] Sorting (Heap sort)

우리는 보통 알고리즘을 공부할 때 가장 많이 다루는 게 바로 정렬 알고리즘이다. 왜 이렇게 중요하게 여겨질까? 그 이유는 프로그램 자체에서 정렬된 정보를 원하는 경우가 많고, 대부분의 알고리즘의 기초를 다질 수 (basic building block)가 있으며, 알고리즘에서 sorting 이 key subroutine으로 종종 사용되기 때문이다.

 

insertion, merge sort

 

우리는 지금까지 analysis, divide and conquer 등 알고리즘에 대해 공부해 나가면서 항상 정렬 알고리즘을 다뤄왔다. 지금까지 다룬 알고리즘 중 insertion sort, merge sort는 각각의 장단점이 존재한다. 먼저 insertion sort는 $O(n^{2})$의 다소 느린 계산 속도를 가지고 있으나 추가 메모리 공간이 필요하지 않은 (in-place) 알고리즘이고, 반대로 merge sort는 $\Theta(n · lg n)$의 빠른 계산 속도를 가지고 있으나 추가적인 메모리 공간이 필요하다.

 

heap

 

예상했겠지만 이번 시간에 다룰 Heapsort는 $\Theta(n · lg n)$의 시간 복잡도를 가지면서 추가적인 메모리 공간이 필요하지 않다. 다만 Heapsort를 구현하기 위해서는 우선순위 큐 (Priority queue)라는 새로운 데이터 구조에 대해 알아야 한다.

 

heap은 먼저 완전 이진트리 (complete binary tree)에 아주 근접한 배열 객체이다. 요소의 개수는 항상 2의 거듭제곱 꼴이 될 수 없기 때문이다. 힙으로 사용할 배열 A에는 두 가지 특성이 존재한다. 배열의 길이 (A.length), 그리고 배열의 힙의 사이즈 (A.heap_size)이다. 둘은 얼핏 보면 비슷해 보이지만 배열의 길이는 배열에 들어 있는 요소의 개수를 의미하고, 힙의 사이즈는 그중 힙으로 사용되는 요소들의 개수이다. 따라서 힙의 사이즈가 배열의 길이보다 작거나 같을 수밖에 없다.

 

접근

힙의 이동경로는 부모로 향하기, 그리고 왼쪽, 오른쪽 서브 트리로 향하기 해서 총 세 가지이다. 우리는 배열을 힙으로 사용하므로 어떤 요소의 인덱스를 2로 나눈 후 버림을 하면 부모 노드의 인덱스가 나오고, 왼쪽/오른쪽 서브 트리의 인덱스는 현재 인덱스의 2배 후 1을 더하거나 아니거나로 나타낼 수 있다. 위 그림을 보면 알겠지만 인덱스 접근의 편의를 위해 배열의 첫 번째 요소의 인덱스는 1부터 시작한다.

 

최대 힙, 최소 힙

 

다음으로 알아볼 것은 힙의 종류이다. 우선순위에 따라 최대가 맨 앞으로 오는 최대 힙, 그리고 최소가 맨 앞으로 오는 최소 힙을 구현할 수 있다. 어떤 식으로 비교하느냐에 따라 다양한 기준으로 우선 순위 큐를 만들 수 있다는 것도 당연한 사실이다. 중요한 것은 모든 경우에서 한 계층 내의 우선순위는 정할 수 없고, 계층 간의 우선순위만을 정할 수 있다는 점이다. 모든 비교는 부모와 자식 간에서 이루어진다.

$$ Max-heap = A[PARENT(i)] \leq A[i] $$

$$ Min-heap = A[i] \leq A[PARENT(i)] $$

 

Time complexities

 

다음으로 알아볼 것은 각 연산의 시간 복잡도이다.

 

Max-heapify - 특정 인덱스로부터 그 아래로 우선순위에 맞게 정렬한다. 재귀적으로 다음 계층의 인덱스를 호출하므로 시간 복잡도는 $O(lg n)$이다.

 

Build-max-heap - 전체 힙의 개수의 반에 해당하는 인덱스부터 루트 인덱스 (1)까지 Max-heapify를 실행시킨다. 따라서 $O(n)$의 시간 복잡도를 가진다.

 

Heapsort - 계층 별로 우선순위에 맞게 정렬을 하는 Build-max-heap을 실행시키고, n-1번만큼 Max-heapify를 실행하므로 $O(n·lg n)$ 의 시간 복잡도를 가진다.

 

그 외에 삽입, 최댓값 추출, 최댓값 출력, 특정 인덱스에 요소 삽입 등 모든 연산은 $O(lg n)$의 시간 복잡도를 가진다.