[자료구조] 7.Sorting: Heap Sort

Heap sort

 

void adjust(int list[], int root, int n) {
	int rootkey = list[root], child = 2 * root;

	while (child <= n) {
		if ((child < n) && (list[child] < list[child + 1]))
			child++; //오른쪽 자식이 더 크면 child++하여 오른쪽자식을 가리킴
		if (rootkey > list[child]) break; //그 자식보다 rootkey가 크면 멈춤
		else {//자식이 rootkey보다 큰 경우
			list[child / 2] = list[child]; //자식을 위로 보냄
			child *= 2;
		}
	}
	list[child / 2] = rootkey; //rootkey 입력
}
void heapsort(int list[], int n) {
	int i, j;
	int temp;

	for (i = n / 2; i > 0; i--) {//n/2는 자식을 가지는 가장 끝의 값
		adjust(list, i, n);//i번째 값을 가지고 maxheap 구성함
	}
	for (i = n - 1; i > 0; i--) {
		SWAP(list[1], list[i + 1], temp);//root의 값을 꺼내 맨 끝으로 보냄
		adjust(list, 1, i);//흐트러진 heap을 재조정함
	}
}

 

heapsort의 첫 번째 반복문

for(i=n/2; i>0;i--)

    adjust(list,i,n);

 

의 과정을 그림으로 설명하겠다.

 

인덱스가 n/2인 것은 자식을 가지는 가장 끝의 노드이다.

n/2를 선택하고,

n/2의 자식노드들과 비교해서 maxHeap을 구성한다.

 

그 다음 i의 값을 1 감소시키고, 그 위치에서도 마찬가지로 maxheap을 구성하도록 한다.(3번과정)

그 다음에도 i의 값을 1 감소시켜 똑같이 반복한다.(4번과정)

 

그다음 또 i를 1 감소시켜 똑같이 반복하고, 또 또 i를 감소시켜 반복한다.

그럼 root가 가장 큰 수를 가지는 maxHeap이 구성된다.

 

 

이제 코드의 두 번째 반복문,

for (i = n - 1; i > 0; i--) {
    SWAP(list[1], list[i + 1], temp);
    adjust(list, 1, i);

}을 보자

 

앞선 과정들로 root가 가장 큰 값을 가지는 maxHeap이 구성되었다. 여기서 root와 heap의 가장 끝의 값과 바꾼다.

 

 

그럼 MaxHeap 구성이 흐트러지게 되는데, (root에는 가장 큰 수가 있어야 하는데 지금 5가 들어옴)

이 root를 자식들과 비교하면서 더 큰수를 위로 올리고 root의 값을 밑으로 내리는 과정을 진행한다.

이 과정을 거치면 다시 MaxHeap이 구성된다. 

(아까 swap으로 가장 큰 값을 맨 밑으로 내린건 다시 건들지 않음. (그림의 숫자 88))

 

 

그 다음 또 MaxHeap이 구성 되면 가장 큰 값 root를 말단으로 보내고, heap을 재조정한다.

이 과정을 끝까지 반복한다.

 

결국 오름차순 정렬이 된다.

 

---

Heapsort는 mergesort에 비해 메모리도 덜 사용하면서, 평균적으로도 물론 최악에도 O(nlogn)시간복잡도를 유지한다.

하지만... 장점만 있을 수는 없는 법

heap sort는 stable하지 않다는 단점이 있다.

 

	최선	평균	최악	Memory	Stable
선택 정렬	n^2	n^2	n^2	1	X
삽입 정렬	n	n^2	n^2	1	O	선택정렬에 비해 데이터의 swap이 많이 발생
퀵 정렬	nlogn	nlogn	n^2	logn, or n	X
병합 정렬	nlogn	nlogn	nlogn	n	O	메모리 공간 많이 필요함
힙 정렬	nlogn	nlogn	nlogn	1	X