[알고리즘] 힙 정렬 (Heap Sort)

기본 개념

- 히프 정렬은 히프 자료구조의 장점인 최대값을 삭제하거나 임의의 값을 삽입하는 연산을 수월하게 하는 점을 이용한 정렬이다.

히프

• 히프는 완전 이진 나무로 나무의 각 노드의 값은 그 노드가 자식 노드를 갖는 경우에 자식의 값보다 크거나 같아야 한다.
• 각 노드의 값이 자식 노드의 값보다 작거나 같도록 히프를 구성할 수 도 있는데 이를 최소값 히프라 한다.
• 각 노드의 값이 자식 노드의 값보다 크거나 같은 히프는 최대값 히프라고 한다.

 

히프 정렬은 두 단계로 구성된다.

• 첫째 단계에서 정렬하려는 1차원 배열을 히프로 변환한다.
• 두 번째 단계에서는 가장 큰 값, 두 번째로 큰 값 등을 차례로 히프에서 제거하면서 키를 정렬한다.

 

첫째 단계. 히프로의 변환 과정

• n개의 키로 구성된 1차원 배열을 히프로 변환하는 방법에는 두 가지 방법이 있다.

 

첫 번째 방법

 

• 삽입 정렬과 비슷한 방법을 사용하여 a[0:i-1] 이 이미 히프 구조를 하고 있는 상태에서 a[i]를 정당한 위치에 삽입하여 a[0:i] 역시 히프 구조를 갖도록 한다. 
• 즉. a[i] 의 제자리를 찾기 위해 a[i]는 자신의 부모노드와 그 크기가 비교되고, 부모노드보다 크면 부모노드와 자리바꿈을 한 후, 다시 그위의 노드와 비교를 하게 된다. 
• 이렇게 트리를 거슬러 올라가면서 자신의 조상 노드들과 자리바꿈을 계속해 가면서 제자리를 찾는다.

두 번째 방법

 

• 배열 전체를 하나의 완전 이진 트리로 간주하고 잎(leaf) 노드로부터 뿌리(root) 노드에 이르기까지 한 레벨씩 트리를 거슬러 올라가면서 트리의 아래 부분이 히프 구조를 가지도록 하는 것이다.
• n개의 노드를 갖는 완전 이진 나무는 [n/2] 개의 잎 노드를 가지며 이 잎 노드를 뿌리로 하는 [n/2] 개의 노드 한 개짜리 나무들은 이미 각각 작은 히프로 볼 수 있다.
• 이는 1차원 배열 전체를 하나의 트리로 보고 그 트리의 리프가 아니면서 가장 높은 레벨에 있는 노드, 즉 잎을 자식 노드로 갖는 노드부터 시작하여 그 트리의 뿌리에 이르기까지 각 노드를 이미 이루어진 작은 히프들의 뿌리에 삽입하는 것과 같다.

히프로의 변환 과정 - 두 번째 변환 방법을 이용한 변환 과정

두 번째 단계. 최대값을 제거하며 정렬하고 남은 원소로 반복하여 히프를 구성하는 과정

-히프에서 최대값을 제거하고 남아 있는 원소들 만으로 다시 히프를 구성하는 과정을 n-1회 반복하여 히프 정렬을 진행한다.

 

 

코드

void HeapSort(int ary[], int n){
	int i;
	//1차원 배열을 히프로 변환
	// n/2 -> n/2-1 ->...-> 1
	//배열 전체를 완전 이진 나무로 간주하고 리프(잎) 노드부터 뿌리노드까지 한 레벨씩 거슬러 올라가면서
	//트리 하단 부분부터 히프 구조를 가지도록 함
	//n개의 노드를 갖는 완전 이진 노드는 n/2개의 잎 노드를 가짐
	printf("--------1차원 배열을 히프로 변환--------\n");
	for (i = n / 2; i > 0; i--) {
		MakeHeap(ary, i - 1, n - 1);
		pirntHeap(ary, 10);
	}
	printf("-----------남은 원소 히프 구성-----------\n");
	//히프에서 최대값을 제거하고
	//남은 원소들로 다시 히프 구성 (n-1)회 반복
	for (i = n-1 ; i > 0; i--) {
		swap(ary[0], ary[i]);
		MakeHeap(ary, 0, i - 1);
		pirntHeap(ary, 10);
	}
}

void MakeHeap(int a[], int root, int lastNode) {
	int parent, leftSon, rightSon, son, rootValue;
	parent = root; 
	rootValue = a[root];
	leftSon = 2 * parent + 1; 
	rightSon = leftSon + 1;
	while (leftSon <= lastNode) {
		if (rightSon <= lastNode && a[leftSon] < a[rightSon])
			son = rightSon;
		else
			son = leftSon;
		if (rootValue < a[son]) {
			a[parent] = a[son];
			parent = son;
			leftSon = parent * 2 + 1;
			rightSon = leftSon + 1;
		}
		else break;
	}
	a[parent] = rootValue;
}

 

실행 시간

 

초기 히프 구축 시간 = O(n)

Makeheap에 걸리는 시간 = 뿌리의 높이 = O(lgn)

전체 히프 정렬 시간 복잡도 = O(nlgn)

 

특징

제자리 정렬

불안정한 정렬