[백준] 2751번 문제 HeapSort구현

백준 2751번 문제도 풀고 HeapSort도 구현해보기위해서 HeapSort를 구현해서 백준 2751 문제를 풀었습니다.

각 함수별 기능 설명

swap함수 : 두 배열의 원소를 바꿔주는 함수입니다.

parent, left_child, right_child는 각각 부모 , 왼쪽 자식, 오른쪽 자식노드를 찾아주는 함수입니다.(없어도 무방합니다.)

FixHeap 함수 : 이 함수는 down Heap을 실행하는 함수로 시작노드에 있는함수를 있어야할 위치까지 내리는 함수입니다. 

consturctHeap 함수 : 이 함수는 주어진 배열을 Heap으로 만들어주는 함수입니다. (아래 코드의경우엔 MaxHeap입니다.)

HeapSort 함수 : Heap의 Root에 있는 노드를 배열 끝에 넣고 FixHeap시키는 함수입니다. 

HeapSort 실행과정에대해 설명하겠습니다.

1. Root노드와 맨마지막 자식노드인 6을 교체하고 Root노드를 배열 끝에 넣습니다(다른 배열에 넣어도 무방)

2. Root노드에 올라온 크기 6인 자식노드를 FixHeap으로 원래 위치까지 내려줍니다.

이과정을 Sort가 완료될때까지 반복하게 됩니다.

Worst Case time Complexity

ConstructHeap : O(n)

FixHeap : O(2logn)

이므로 Heapsort의 시간복잡도는 O(n) + O(2logn) 즉 O(logn)과 같습니다.

이떄 FixHeap은 FixHeapFast를 통해 더 빨리 실행할수있습니다.

해당코드는 FIxHeapFast가 아닌 FixHeap함수입니다.

* 해당 코드는 1번 index부터 사용해서 left_child = 2*i , right_child = 2*i + 1으로 구성이됩니다.

#include 

using namespace std;

void swap(int* a, int* b) {
	int t = *a;
	*a = *b;
	*b = t;
}

int parent(int a) {
	return (a / 2);
}

int left_child(int a) {
	return 2 * a;
}

int right_child(int a) {
	return (2 * a + 1);
}

void FixHeap(int* arr, int node, int key, int max_size) { // MinHeap
	if (node * 2 > max_size) { // Leaf일 경우
		arr[node] = key;
	}
	else {
		int largest = node;
		int left = left_child(node);
		int right = right_child(node);

		if (left <= max_size && arr[left] > arr[largest]) largest = left;
		if (right <= max_size && arr[right] > arr[largest]) largest = right;

		if (largest != node) {
			swap(arr[node], arr[largest]); 
			FixHeap(arr, largest, arr[largest], max_size);
		}
		
	}

	return;
}

void constructHeap(int* arr, int node, int max_size) {
	int K;
	if (left_child(node) <= max_size) { // Leaf가 아닐경우
		constructHeap(arr, left_child(node), max_size);
		constructHeap(arr, right_child(node), max_size);
		K = arr[node];
		FixHeap(arr, node, K, max_size);
	}
}

void heapSort(int* arr, int node, int size) {
	constructHeap(arr, node, size);
	
	for (int last_leaf = size; last_leaf >= 2; last_leaf--) {
		swap(&arr[1], &arr[last_leaf]);
		FixHeap(arr, 1, arr[1], last_leaf - 1);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	int C;
	cin >> C;
	int *arr = new int[C];

	for (int i = 1; i <= C; ++i) {
		cin >> arr[i];
	}

	heapSort(arr, 1, C);

	for (int i = 1; i <= C; ++i) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

HeapSort에서 FixHeap을 실행할때 Size를 한칸씩줄이는 이유는 추가적인 배열을 사용하지않고 배열 맨끝에 가장 큰값을 넣기위해서입니다.