[정렬 알고리즘] 04 힙 정렬(Heap Sort) 이론 및 구현

1. 힙 정렬 개념

• 자료구조인 힙(Heap)의 사용하여 정렬을 수행하며 여기서는 최대 힙을 사용
• 입력 자료들을 최대 힙으로 구성(Build-Max-Heap : 정렬되지 않은 입력 자료들로부터 최대 힙을 만듦)
• 최대 힙을 구성하는 과정에서 힙 특성을 유지하는 역할이 포함되어야함(Max-Heapify : 힙 특성 유지)
• 구성된 최대 힙에서 Root부터 차례대로 힙에서 꺼내어 저장(Heap-Sort : 배열을 내부 정렬함)
  

※ 힙(Heap) 추가 개념

• 힙(Heap) : 완전 이진 트리이며 최대 힙과 최소 힙이 존재
• 완전 이진 트리(Complete binary tree) : 각각의 노드가 최대 두 개의 자식 노드를 가지며 자식 노드를 추가할 때 왼쪽부터 차례대로 채우는 트리
• 노드의 높이 : 해당 노드에서 리프에 이르는 하향 경로중 가장 긴 것의 간선 수
• 힙의 높이 : 루트의 높이 -> $O(\lg n)$
• 최대 힙 : 부모 노드가 자식 노드보다 큰 경우
• 최소 힙 : 자식 노드가 부모 노드보다 큰 경우

배열로 표현 가능

+) 두 가지 특성

• length[A] : 배열의 원소 갯수
• heap-size[A] : 힙 정렬이 되어있는 A배열의 원소 갯수
• heap-size[A] $\le$ length[A]

---

2. 힙 정렬 예제

① Max-Heapify : 최대 힙에서 힙 특성에 위반되는 원소의 값을 내려보냄으로 최대 힙 특성 유지

힙 특성 유지 과정

② Build-Max-Heap : 최대 힙을 만듦, 리프 노드보다 한 단계 위의 노드부터 루트 노드까지 올라감

③ Heap-Sort : 최대 힙의 루트 노드부터 차례대로 꺼내면서 저장, 삭제할 경우 힙 크기에서 '-1'을 해줌
(루트 노드와 힙의 마지막 노드와 교체한 후 삭제, 삭제한 뒤에는 힙 특성을 유지시켜줘야함)

루트 노드 제거 과정

---

3. 힙 정렬 특성

1) 장점

• 부가적인 메모리가 필요 없음
• 어떠한 입력 데이터에 대해서도 최대 복잡도 $O(n \lg n)$을 보장

2) 단점

• 실제 프로그램에서 실행할 경우 평균적인 계산 속도에서 퀵 정렬보다 늦고 안정되지 못함

---

4. 힙 정렬 분석

① MAX-HEAPIFY / 힙 특성 유지하기

▶ Pseudo code(의사코드)

* 입력 : 배열$A$, 배열의 인덱스 $i$
* 설명 : 최대 힙 $A[i]$값을 "내려보냄"으로써 인덱스 $i$를 루트로 하는 서브 트리가 최대 힙이 되도록 한다.
* 수행시간 :
- 원소 $A[i], A[LEFT(i), A[RIGHT(i)]$사이의 관계를 결정하는 시간 $\theta(1)$과 노드$i$의 자식 중 하나를 루트로 하는 서브 트리에서 MAX-HEAPIFY를 실행하는 시간을 더한 것.
- 자식들의 서브 트리는 최대 크기가 $2n/3$ (최악의 경우 : 트리의 마지막 줄이 정확히 절반 차있을 때 -> 밑에 추가 설명함)

 

$\therefore T(n) \le T(2n/3) + \theta(1)$

※ Max-Heapify에서 서브 트리가 $2n/3$일 때 최악의 경우인 이유

 

② BUILD-MAX-HEAP / 힙 만들기

▶ Pseudo code(의사코드)

배열 $A[1,...n]$을 최대 힙으로 바꿀 경우, MAX-HEAPIFY프로시저를 바닥에서부터 위로 올라가는 식으로 이용($n=A.length$)
위 의사코드 2번째 줄은 $A[(\left\lfloor n/2\right\rfloor+1) ... n]$의 원소를 의미하며 즉, 리프노드를 뜻함
따라서, $\left\lfloor A.length/2 \right\rfloor$ 즉, 힙 사이즈의 맨 오른쪽 노드부터 MAX-HEAPIFY를 수행

* 수행시간 : 
MAX-HEAPIFY 한 번 호출할 때마다 $O(\lg n)$시간 걸림
MAX-HEAPIFY 호출 횟수는 $O(n)$ -> $n$개의 입력 값 들어왔을 때

$\therefore O(n\lg n)$

하지만, 위 시간 복잡도는 MAX-HEAPIFY의 수행시간이 노드의 높이에 따라 다른 것을 고려하지 않았음

+) 좀 더 정확하게 구하기 위해
MAX-HEAPIFY의 수행시간이 노드의 높이에 따라 다르고 노드 대부분의 높이가 작다고 고려

• 원소가 n개인 힙의 높이 : $\left\lfloor \lg n \right\rfloor$
• 높이가 h인 노드 수는 최대 : $\left\lceil n/2^{k+1} \right\rceil$
• 높이가 h인 노드에서 호출될 때 MAX-HEAPIFY의 수행시간 $O(h)$

 

③ HEAP-SORT / 힙 정렬

▶ Pseudo code(의사코드)

* 1번째 줄 : BUILD-MAX-HEAP(A)는 $O(n)$
* 2번째 줄 : n-1번 실행
* 3~4번째 줄 : 루트 노드와 마지목 노드를 교체 후 간선을 없애므로 $O(1)$
* 5번째 줄 : MAX-HEAPIFY(A, i)는 $O(\lg n)$

$T(n) = O(n) + n \cdot (O(1) + O(\lg n))$ = $O(n) + O(n) + O(n\lg n)$

$\therefore O(n\lg n)$

---

5. 힙 정렬 시간 복잡도

1) Worst Case

• 완전 이진트리가 포화상태인 경우에서 왼쪽 서브트리가 전체의 절반인 자식노드가 생겼을 경우
• 즉, 리프노드가 절반만 차있을 경우 최악의 경우 $2n/3$ (왼쪽 서브트리) <-> $n/2$ (오른쪽 서브트리)

① Max-Heapify : $T(n) = T(2n/3) + \theta(1)$ -> $O(\lg n)$
② Build-Max-Heap : Max-Heapify의 수행시간이 노드의 높이에 따라 다르고 노드 대부분 높이가 작은 경우 -> $O(n)$
③ Heap-Sort(Build-Max-Heap을 제외한 나머지는 n번 실행)

• Build-Max-Heap : $O(n)$
• delete-root & switching with last node : $O(1)$
• Max-Heapify : $O(\lg n)$

$T(n) = O(n) + n \cdot (O(1) + O(\lg n))$ = $O(n) + O(n) + O(n\lg n)$

④ 시간 복잡도 : $O(n \lg n)$

 

2) 성능 및 평가

- 일반적인 경우 $O(n \lg n)$의 시간 복잡도를 가짐

	Best	Avg	Worst
힙 정렬	$O(n \lg n)$	$O(n \lg n)$	$O(n \lg n)$

 

---

6. 힙 정렬 구현(C언어)

#include<stdio.h>
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

void Heap_Sort(int[], int);
void Build_Max_Heap(int[], int);
void Max_Heapify(int[], int, int);

int main()
{
	int length;
	int arr[10] = { 10, 28, 30, 2, 15, 8, 67, 45, 3, 11 };

	length = sizeof(arr) / sizeof(int);	

	Heap_Sort(arr, length);

	return 0;
}

// Heap_Sort 함수
void Heap_Sort(int arr[], int length) {

	int *temp;
	int i;

	Build_Max_Heap(arr, length);			// 먼저 힙을 만든다.
	for (i = length - 1; i >= 0; i--) {
		SWAP(arr[0], arr[i], temp);		// 부모노드와 마지막 노드와 SWAP
		length--;				// 부모노드를 삭제.
		Max_Heapify(arr, 0, length);		// 힙 유지 실시.
	}
}

// Build_Max_Heap 함수
void Build_Max_Heap(int arr[], int length) {

	int parent_position;

	// 리프 노드를 제외한 맨 마지막 노드부터 시작.
    // 배열은 0부터 시작하므로 length/2에 -1을 해줘야함.
	for (parent_position = length / 2 - 1; parent_position >= 0; parent_position--) { 
		Max_Heapify(arr, parent_position, length);	// 힙 유지 실시.
	}
}

// Max_heapify 함수
void Max_Heapify(int arr[], int parent_position, int heap_size) {

	int *temp;
	int left, right, largest;

	left = 2 * parent_position + 1;
	right = 2 * parent_position + 2;

	if ((left < heap_size) && (arr[left] > arr[parent_position])) // 왼쪽 자식 노드와 부모노드 비교.
		largest = left;
	else
		largest = parent_position;

	if ((right < heap_size) && (arr[right] > arr[largest]))	// 오른쪽 자식노드와 이전에 얻은 제일 큰 노드 값과 비교.
		largest = right;

	if (largest != parent_position) {
		SWAP(arr[parent_position], arr[largest], temp);	// 값이 큰 노드를 부모노드로 SWAP.
		Max_Heapify(arr, largest, heap_size);	// 다시 부모노드를 대상으로 Heapify를 실시.
	}
}