[C language] heap sort 힙 정렬

힙 (Heap)

Heap은 완전 이진트리 (complete binary tree)를 기본으로 한다.

완전 이진트리란

이런 식으로 왼쪽정렬된 모습을 하는 트리이다. 자식이 추가되면, 오른쪽에 들어온다.

 

최대힙, 최소힙 ( Max_Heap , Min_Heap )

힙에는 최대힙과 최소힙이 있다.

최대힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 한다.

최소힙은 그 반대이다.

이것이 최대힙의 예시이다.

 

이진 탐색 트리 (Binary Search Tree)와 헷갈릴 수 있으니, 조심해야 한다.

 

힙의 표현

힙은 배열이나 linked list로 만들 수 있다.

 

힙 노드 추가 (insert)

노드를 추가할 땐 오른쪽으로 추가한다.

이런 방식이다.

 

힙 노드 삭제 (delete)

힙 노드를 삭제할 때는 root에서 삭제한다.

이렇게 root에 있는것이 삭제된 후, 맨 오른쪽 노드를 삭제해서 트리 모양을 맞춰준다. 그 뒤, 정렬을 다시 해준다.

 

힙 정렬 (Heap Sort)

힙 정렬을 하기 위해서, 먼저 힙 구조를 만들어 준다.

예를 들어, 배열로 만들었다고 가정한다.

(최대 힙인 경우) 시작점은 배열 갯수의 절반에 해당하는 노드이다. 예를 들어 배열에 10개의 요소가  있다면, 5번 노드부터 시작한다.

5번 노드가 자식보다 크거나 같은지 판별한다.

그 다음은 4번, 3번, 2번, 1번 노드의 순서로 수행한다.

 

최대힙 구하는 과정---------------------------------------------------------------------------------------------------------------------------

예를 들어, 아래와 같이 list 라는 배열이 있다고 가정한다.

우선, 이 배열을 최대힙으로 만들어야한다.

int list[MaxNum] = {15, 3, 10, 5, 4, 8, 9, 7, 2, 1};

시작점은 5번이다. [5]번의 4는 [10]번의 1보다 크기 때문에 더이상 연산할 필요가 없다.

다음은 4번이다. [4]번의 5는 [8]번의 7보다 작다. 따라서 [4]번과 [8]번의 위치를 바꿔준다.

바뀐 후, [4]번은 자식노드가 모두 작으므로 더이상 연산이 필요없다.

다음으로, [3]번을 보면, 자식노드가 모두 작으므로 더이상 연산이 필요없다.

다음으로, [2]번을 보면, [2]번의 3보다 [4]번의 7이 더 크다. 따라서 두 위치를 바꿔준다.

바뀐 후, [2]번을 확인하면 자식노드가 모두 작은것을 확인할 수 있다. 오른쪽 자식인 [4]번을 보면, [8]번의 5가 [4]번의 3보다 큰것을 확인할 수 있다. 이 둘을 또 다시 바꿔준다.

바뀐 후 [4]번 노드를 보면, [8]번과 [9]번 모두 작은것을 알 수 있다.[9]번을 수행한 후, [9]번에는 자식노드가 없으므로 연산을 종료한다.

다음으로는  [1]번 노드를 본다. 자식노드가 모두 작으므로 더이상 연산이 필요없다.

 

----------------------------------------------------------------------------------------------------------------------------------------------

 

이렇게 최대힙을 구했다.

이 최대힙의 root는 list배열의 최댓값이 된다.

이렇게 계속해서 최대힙을 구성하면서 list배열의 최댓값을 얻어서 정렬을 하는것이 heapsort이다.

 

즉, HeapSort란,

배열을 최대(최소)힙으로 구현 --> root의 값이 배열의 최대가 됌 --> 이 두 동작을 반복해서 정렬함.

 

HeapSort 구현

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

void printarr(int a[]) {
	printf("배열 : ");	
	for (int i = 1; i < 12; i++) 
		printf("%d ", a[i]);
	printf("\n");
	
	/****     tree      *****/
	printf("                             Tree\n");
	printf("                             %d\n", a[1]);
	printf("             %d                               %d\n", a[2], a[3]);
	printf("    %d              %d              %d              %d\n", a[4], a[5], a[6], a[7]);
	printf("%d    %d      %d     %d", a[8], a[9], a[10], a[11]);

	printf("\n\n\n\n\n\n\n\n\n\n");
}

void adjust(int a[], int root, int n) {
	int child, rootkey, temp;
	temp = a[root];
	rootkey = a[root];
	child = 2 * root;
	while (child <= n) {
		if ((child < n) && (a[child] < a[child + 1]))
			child++;
		if (rootkey > a[child])
			break;
		else {
			a[child / 2] = a[child];
			child *= 2;
		}
	}
	a[child / 2] = temp;
}

void heapSort(int a[], int n) {
	int i, j, temp;

	for (i = n / 2; i > 0; i--) {
		adjust(a, i, n);
		printarr(a);
	}
	for (i = n - 1; i > 0; i--) {
		SWAP(a[1], a[i + 1], temp);
		adjust(a, 1, i);
		printarr(a);
	}
}

int main() {

	int a[12] = { NULL, 1243, 5643, 6542, 5678, 3945, 2346, 9493, 8234, 7398, 3453, 3947 };

	heapSort(a, 11);

	return 0;
}

 과제로 했던 코드이다.

 

 

 

----------------------------------------------------------------------------------------------------------------------------

ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/

힙 정렬(Heap Sort) · ratsgo's blog

설명을 위해 참고한 글

----------------------------------------------------------------------------------------------------------------------------