[자료구조] 상향식 힙정렬 heapsort

안녕하세요 주인장 H입니다. 

오늘은 힙정렬에 대해 알아보겠습니다. 

 

힙정렬은 힙트리구조를 이용하여 정렬을 하는 방법입니다. 

힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리입니다. 

여기서 완전 이진트리란 부모노드(root)에 2개의 자식노드(c)를 가진 형태를 말합니다. 

힙에는 최대힙과 최소합이 존재하고, 최대 힙은 부모노드가 자식노드보다 커야합니다. 

 

힙정렬을 하기위해선 정해진 데이터를 힙구조로 만든 후에 시작해야 합니다. 

힙 정렬을 수행하기 위해선 힙 생성 알고리즘(heapifiy Algorithm)을 사용합니다. 

특정 노드의 두 자식 중 더 큰 자식과 자신을 바꾸면 됩니다. 

 

예를 들어 

   1

 4    9

2 3 4 4 

 

   9

 4    4

2 3 4 1 

로 힙구조를 만들고 특정 노드 9와 1을 서로 바꾸어 줍니다 

 

   1

 4    4

2 3 4  9

그 후 9를 제외한 다른 노드들을 다시 최대항을 만들어주는 것을 반복하면

 

    2

 3    2

4 4 4  9  

의 형태로 정렬이 될것입니다. 

 

그럼 위에서부터 차례대로 인덱스에 넣어주면 되겠죠. 

이때 힙정렬의 전체 시간 복잡도는 

힙생성 알고리즘의 시간복잡도가 O(log N)이고 전체 데이터의 갯수가 N이므로 

O(log N * N)이 되겠습니다. 

#include <stdio.h>
#define HEAPSIZE 9

int heap[HEAPSIZE] = { 1,5,3,6,2,6,6,4,9 };

//힙 구조 만들기 

int main(void) {
	for (int i = 1; i < HEAPSIZE; i++) {
		int c = i; 
		do {
			int root = (c - 1) / 2;
			if (heap[root] < heap[c]) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			} c = root; 
		} while (c != 0);
	}
	//크기를 줄여가며 힙 정렬
	for (int i = HEAPSIZE - 1; i >= 0; i--) {
		int temp = heap[0]; 
		heap[0] = heap[i]; 
		heap[i] = temp; 
		int root = 0; 
		int c = 1; 
		//자식 중에 큰 값이 있는지 확인 
		do {
			c = 2 * root + 1; 
			if (c < i - 1 && heap[c] < heap[c + 1]) {
				c++;
			}
		//root 값이 더 크다면 교체 
			if (c < i && heap[root] < heap[c]) {
				temp = heap[c];
				heap[c] = heap[root];
				heap[root] = temp; 
			}
			root = c; 
		} while (c < i);
	}
	for (int i = 0; i < HEAPSIZE; i++) {
		printf("%d ", heap[i]);
	}
	return 0;
}