[자료구조] 힙 정렬 (heap sort)

힙 정렬이란?

힙 정렬은 힙 트리를 이용해 정렬을 하는 것을 말합니다.

 

사실 최대 힙과 최소 힙은 각각 루트에 최댓값과 최솟값이 이미 있습니다.

루트를 계속 꺼내면 힙의 정의에 의해 그 다음 큰 값(혹은 작은 값)이 계속 루트에 상주하게 됩니다. 따라서 트리에 노드가 없을 때까지 힙 트리의 삭제 함수를 계속 호출만 하면 됩니다.

 

힙 정렬에는 최대 힙과 최소 힙 중 어느 것을 사용할까요? 눈치 채셨겠지만, 상관없습니다. 내림차순으로 정렬하려면 최대 힙을 사용하면 되고, 오름차순으로 정렬하려면 최소 힙을 사용하면 됩니다.

 

예시로 최대 힙을 사용한 힙 정렬을 들어보겠습니다.

힙 트리에 관한 자세한 정보는 아래의 힙 (Heap) 포스팅을 참고하시기 바랍니다.

[자료구조] 힙 (Heap)

 

힙 정렬 구현

힙 정렬의 핵심은 힙 트리 구현입니다. 힙 트리를 구현하는 것 그 자체가 정렬이기 때문이죠. 그저 트리의 root를 빼내기만 하면 됩니다.

 

코드로 구현하면 다음과 같습니다.

void heap_sort(element a[], int n) {
	for(int i = n - 1; i >= 0; i--) {
		a[i] = delete_max_heap(h);
	}
}

보면 알 수 있듯이, 그냥 함수 내에서는 반복문으로 root 값을 빼내는 것 말곤 하는 것이 없습니다.

 

힙 정렬의 시간복잡도

힙 정렬의 시간복잡도는 힙의 재구성 시간에 따라 달려있습니다.

 

힙 트리에서 root를 삭제하게 되면 이를 채우기 위해 (최악의 경우) 트리의 높이만큼 연산을 실행하게 되고 $O(log \space n)$의 시간이 소요됩니다.

이를 노드의 개수($n$)만큼 해야 하므로 총 시간복잡도는 $O(n \space log \space n)$입니다.

 

 

[자료구조] 선택 정렬 (selection sort)

[자료구조] 삽입 정렬 (insertion sort)

[자료구조] 버블 정렬 (bubble sort)

[자료구조] 셸 정렬 (shell sort)

[자료구조] 합병 정렬 (merge sort)

[자료구조] 퀵 정렬 (quick sort)

[자료구조] 기수 정렬 (radix sort)