Heap sort 소개

자료구조 시간에 Heap에 대해 이미 들어봤다.

마지막 level의 노드를 제외한 모든 노드가 채워진 완전 이진 트리이고, 모든 노드는 왼쪽부터 순서대로 채워진다.
또한 Max heap의 경우 부모 노드는 자식보다 크거나 같고, Min heap의 부모 노드는 자식 노드보다 작거나 같다.

 

이런 특징을 갖는 힙은 배열로 구현 가능하다. (자료구조에서 배웠듯이 완전 이진 트리이기 때문에..)

그림의 배열을 보면 왜 배열로 구현할 수 있는지 알기 쉽다.
예를 들어 트리의 4번째 노드를 보자. 트리의 4번째 노드의 왼쪽 노드엔 8번째 노드, 오른쪽 노드에는 9번째 노드가 들어있다.
이제 트리 말고 배열을 봐보자. 아까 말했던 4번째 노드의 Left는 return 2i 이므로 배열의 8번째 공간에 값 2가 들어가있고, 오른쪽은 return 2i + 1 이므로 9번째 공간에 4가 할당됐다.

이렇게 힙을 배열로 구현할 수 있다.

 

 

이제 이것을 정렬 알고리즘으로 사용하기 위해 핵심이 되는 연산인 Max - Heapify에 대해 알아보자.

"Max heapify"는 힙 자료구조 형태를 유지하면서, 주어진 특정 노드를 "max heap"의 성질을 만족하도록 하는 연산을 말한다.

조금 풀어서 말하자면 이 연산은 주어진 노드의 자식들 중에서 가장 큰 값을 가진 노드를 찾아 그 노드와의 위치를 교환하며, 이 과정을 재귀적으로 수행하여 해당 노드가 max heap의 조건을 만족하도록 한다.

다음은 Max-Heapify 연산의 슈도코드이다.

Max-Heapify(A,i)
l = Left(i)
r = Right(i)
if l <= A.heap-size && A[l] > A[i]
	largest = l
else largest = i
if r <= A.heap-size && A[r] > A[largest]
	largest = r
if largest != i
	swap A[i],A[largest]
	Max-heapify(A,largest)

현재 힙 배열의 크기를 넘는지 아닌지 l, r 인덱스로 비교하고, 자식노드들을 비교해서 largest value값의 index를 찾는다.

이 연산을 사용하면 아래의 그림과 같이 배열이 이동한다.

이 때, Max-Heapify의 시간복잡도 T(n)은 높이 h가 log n이기 때문에 O(1) * O(h) = O(log n)이다.

 

 

Max-Heapify 외에 Heap 알고리즘을 구성하는 또 다른 핵심 연산 build-max-heap도 있다.

주어진 배열을 max heap으로 만들기 위해서는 배열의 각 요소를 힙으로 삽입하는 것보다 더 효율적인 방법이 필요한데, 여기서 build-max-heap연산을 사용한다.

이 연산은 완전한 힙 구조는 아니지만, 부모 노드가 자식 노드보다 크거나 같은 값을 갖는 상태로 만들고, 그 후에는 배열을 완전한 힙 구조로 만들기 위해 max heapify 작업을 수행한다.

아래는 build-max-heap의 슈도 코드이다.

Build-Max-Heap(A)                      // O(n log n)
A.heap-size = A.length        
for i = [A.length/2] downto 1          // O(n)
	Max-Heapify(A,i)               // O(log n)

 

이 연산을 사용하면 아래와 같이 bottom-up 방식으로 Max-Heapify 절차를 밟으며 배열이 이동한다.

여기서 Max-Heapify의 시간복잡도는 O(log n)이고, Max-Heapify 호출의 수는 O(n/2),
그러므로 슈도코드에 따라 build-max-heap의 총합 시간복잡도는 O(n log n)이다.

그런데.. build-max-heap 의 upper bound로 O(n log n)이 맞긴 하지만.. 점근적으로 tight하게 근사하진 않는다.
만약 tighter bound를 구하고 싶다면.. 다음과 같이 식을 유도할 수 있다.

이 식은 결국 O(n)이라는 tight한 bound를 얻었다.

 

정리하자면,  build-max-heap 연산의 upper bound를 만족하는 시간 복잡도는 O(n log n)이고, tight하게 구하기 위해 미분을 해보면 O(n)의 선형 시간 안에 처리할 수 있다는 것을 증명하는 내용이다.

 

마지막으로 Heap sort의 처리 과정을 알아보고 heap sort를 끝내자

Heapsort(A)
Build-max-heap(A)
for i = A.length downto 2
	swap A[1],A[i]
    	A.heap-size = A.heap-size -1
    	Max-heapify(A,1)

이와 같은 슈도코드를 따라서 배열을 정렬해보면 다음의 처리과정을 확인할 수 있다.