(https://www.youtube.com/watch?v=iyl9bfp_8ag&t=953s 를 기반으로 정리했습니다.)

힙 정렬 알고리즘이란 ?

먼저 이진트리중 완전 이진트리에 대해 알아야하는데 컴퓨터가 데이터를 표현하는 방식으로 각 노드에 두개의 하위노드를 가지는 데이터 구조로써 최상위 부모 node는 root 라고 하며 최 하위 노드는 리프라고 한다.(하위 노드는 좌측부터 생성된다.)

heap 이란 ?

최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최소 힙이있는데 최대 힙은 부모노드가 하위노드보다 큰 값으로 이루어진 노드를 말한다.

노드가 붕괴될때 힙 생성 알고리즘을 사용하는데 이를 Heapify Algorithm 이라고 한다.

먼저 데이터들을 최대힙 또는 최소힙으로 만들어준다.

int number = 9;
int heap[9] = { 7,6,5,8,3,5,9,1,6 };
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);

}

이렇게 하면 최대힙을 구성하도록 배열에 데이터가 생성됐을것.

이후 최 하위 오른쪽에 있는 노드와 루트를 바꿔준다. 이렇게 하면 가장 큰 값이 가장 뒤로 가게되며 이를 반복할 시 정렬을 수행할 수 있는것.

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++;
		}
		//루트보다 자식값이 더 크고 c 가 i 범위를 벗어나지 않았다면 ~ 
		if (heap[root] < heap[c] && c < i) {
			int temp = heap[root];
			heap[root] = heap[c];
			heap[c] = temp;
		}
		root = c; 
	} while (c < i);

}