6. 힙 정렬 (Heap Sort)

 

#include <iostream>
using namespace std;

void heapify(int arr[], int N, int parent) {
	int child1 = parent * 2 + 1, child2 = parent * 2 + 2;
	int Max = parent, temp = 0;

	if (child1 < N) {
		if (arr[parent] < arr[child1])Max = child1;
	}
	if (child2 < N) {
		if (arr[parent] < arr[child2]) {
			if (arr[child1] < arr[child2]) {
				Max = child2;
			}
		}
	}	

	if (Max != parent) { //부모가 자식보다 더 작으면 교환한다
		temp = arr[Max];
		arr[Max] = arr[parent];
		arr[parent] = temp;
		heapify(arr, N, Max); //교환 후 그 자식의 자식과 다시 비교를 위해 재귀
	}
}

void heapSort(int arr[], int last) { //힙 정렬
	for (int i = N - 1; i >= 0; i--) {
		//루트와 마지막 노드를 교환한다
		int temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
		heapify(arr, i, 0); //마지막 노드를 제외한 뒤 루트를 기준으로 heapify 시킨다
	}
}

int main() {
	int arr[6] = {1, 12, 9, 5, 6, 10};
	int N = 6;
	
	for (int i = (N - 1) / 2; i >= 0; i--) heapify(arr, N, i); //초기 최대 힙 구조로 만든다

	heapSort(arr, N); //최대 힙이므로 오름차순 정렬

	for (int i = 0; i < N; i++) cout << arr[i] << "\n";

	return 0;
}