6. 힙 정렬

힙 정렬

힙 정렬은 힙 트리 구조를 이용하는 정렬 방법으로, 매우 빠른 알고리즘입니다.

용어 정리

트리

데이터가 나무가 가지를 뻗는 것처럼 서로 연결되어 있는 구조

이진 트리

트리 구조에서 모든 노드의 자식 노드가 2개 이하인 노드

완전 이진 트리

데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 순서대로 들어가는 이진 트리

힙

완전 이진 트리를 기반으로 하는 트리. 최대 힙과 최소 힙 존재.(최솟값을이나 최댓값을 빠르게 찾아내기 위해 사용)
ex) 최대 힙: 부모 노드가 자식 노드보다 큰 힙

힙 정렬을 위해서는 데이터들을 힙 구조로 만들어야한다. 이때 힙 생성 알고리즘을 사용합니다. 힙 생성 알고리즘은 하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태라고 가정하고 사용합니다. 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘입니다. 그리고 자식이 존재하지 않을 때까지 이와 같은 과정을 반복합니다. 이러한 힙 생성 알고리즘의 시간 복잡도는 O(logn)입니다. 힙 정렬은 힙 구조로 만든 데이터에서 가장 큰 값인 루트와 가장 뒤쪽 원소를 바꾼 뒤 그 바꿔진 가장 큰 원소를 제외하고 다시 힙 생성 알고리즘(Heapify)를 적용합니다. 그리고 이와 같은 과정을 반복하여 정렬을 완성시킵니다. 힙 정렬에서는 데이터 N개에 대해 위 알고리즘을 적용하므로 총 시간 복잡도는 O(n*logn)이라고 볼 수 있습니다.

#include <stdio.h>

int number = 9;
int heap[9] = { 7, 6, 5, 8, 3, 5, 9, 1, 6 };

int main() {
	// 전체 트리 구조를 heap구조로 변경
	for (int i = 1; i < number; 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);
	}
	// 크기를 줄여가며 반복적으로 heap 구성
	for (int i = number - 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 (heap[c] < heap[c + 1] && c < i - 1) {
				c++;
			}
			// 루트보다 자식이 더 크면 교환
			if (heap[root] < heap[c] && c < i) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			root = c;
		} while (c < i);
	}

	for (int i = 0; i < number; i++) {
		printf("%d ", heap[i]);
	}

	return 0;
}