개인공부용123 프로그래밍 블로그

BoJ 2751 && Accelerated HeapSort구현 본문

Algorithm/이론

BoJ 2751 && Accelerated HeapSort구현

개인공부용123 2017. 4. 30. 15:29

FixHeapFast를 사용해서 HeapSort를 구현해봤습니다.


각 함수별 기능 설명


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


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


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

단 이떄 FixHeapFast함수는 promote함수를 이용해서 높이의 절반 만큼씩 내려가게 됩니다. 그리고 vacant가 잘못 내려갔을경우 BubbleUpHeap함수를 이용해서 있어야할 위치로 올려줍니다.


Promote 함수 : vacant를 높이의 절반만큼 내리는 함수입니다. (한칸씩 내려감)


BubbleUpHeap 함수 : vacant가 잘못내려왓을경우 부모와 비교하여 알맞은 위치를 찾아 올라가는 함수입니다.


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


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





Accelerated HeapSort 실행과정에대해 설명하겠습니다. (위의 사진이 작아서 잘안보이니 참고만 하시면됩니다..)


빨간색 원으로 표시된부분이 vacant입니다.


1. vacant를 루트로하는 서브트리의 높이 h의 절반만큼 내려간다. (promote함수를 이용)

2. 내려간 후 내려간 위치의 부모와 비교해서 부모보다 크면 BubbleUpHeap 작으면 다시 FixHeapFast를 실행한다.


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


Worst Case time Complexity

ConstructHeap : O(n)


Accelerated HeapSort : O(logn)


HeapSort도 O(logn)인데 뭐가 다르냐 할수있습니다.

하지만 HeapSort의 수행시간은 O(n) + 2*n*logn입니다.

하지만 Accelerated HeapSort의 수행시간은 O(n) +n*logn + n*log(logn)입니다

즉 O(logn)을 O(log(logn))으로 줄일수 있습니다.


해당코드는 FIxHeapFast 입니다.



#include <iostream>
#include <math.h>

using namespace std;

// MAX Heap을 이용해서 오름차순 정렬을 하는 코드 입니다.

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);
}

int promote(int* arr, int hStop, int vacant, int h, int max_size) { // arr = 배열, hStop = 얼마나 내려갈 것인지, vacant = 현재위치, h = 높이(점점내려감)
	int vacStop;// 내려갈 위치

	if (h <= hStop) { // 내려갈만큼 내려갔을경우 현재위치를 리턴시킴
		vacStop = vacant;
	}
	else if (arr[left_child(vacant)] < arr[right_child(vacant)] && right_child(vacant) <= max_size) { // 우측 자식이 더 클 경우
		swap(&arr[vacant], &arr[right_child(vacant)]);
		vacStop = promote(arr, hStop, right_child(vacant), h - 1, max_size);
	}
	else{ // 좌측 자식이 더 클경우
		swap(&arr[vacant], &arr[left_child(vacant)]);
		vacStop = promote(arr, hStop, left_child(vacant), h - 1, max_size);
	}	
	
	return vacStop;
}

void BubbleUpHeap(int* arr, int root, int K, int vacant) { // root = 루트 노드, K = vacant의 원래 값, vacant = 현재 위치 (해당 코드에선 루트 = 1이지만 노드로 들어갈떄 필요하므로 넣었음)
	if (vacant == root) arr[vacant] = K;
	else {
		int Parent = parent(vacant);
		if (K < arr[Parent]) { // 부모 보다 작다면 자기위치를 찾은것
			arr[vacant] = K;
		}
		else { // 부모 보다 크다면 버블업힙을 계속 실행
			swap(&arr[vacant], &arr[Parent]);
			BubbleUpHeap(arr, root, K, Parent);
		}
	}

	return;
}

void FixHeapFast(int* arr, int vacant, int K, int h, int max_size) { // K = vaccant의 원래 값, vaccant = 현재위치(루트), h = 높이
	if (h <= 1) { // h가 1이하일경우
		if (h == 0) return;	
		else {
			if (left_child(vacant) > max_size) return; // h가 1이남았지만 해당노드의 자식이 없을수도있다.

			if (K < arr[left_child(vacant)]) swap(&arr[vacant], &arr[left_child(vacant)]);

			if (arr[vacant] < arr[right_child(vacant)] && right_child(vacant) <= max_size) swap(&arr[vacant], &arr[right_child(vacant)]);
			return;
		}
	}
	else {
		int hStop = h / 2;
		int vacStop = promote(arr, hStop, vacant, h, max_size); // 새로운 위치
		int vacParent = parent(vacStop); // 새로 찾은 위치의 부모

		if (arr[vacParent] < K) {
			swap(&arr[vacStop], &arr[vacParent]);
			BubbleUpHeap(arr, vacant, K, vacParent);
		}
		else FixHeapFast(arr, vacStop, K, hStop, 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);
	
	int h; // 높이 계산

	for (int last_leaf = size; last_leaf >= 2; last_leaf--) {
		swap(&arr[1], &arr[last_leaf]);
		h = log2(last_leaf - 1);
		FixHeapFast(arr, 1, arr[1], h, last_leaf - 1);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	int C;
	cin >> C;
	int *arr = new int[C + 1];
	
	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;

	delete[] arr;
	return 0;
}


약간 이상한점이 있습니다... 이론상 Accelerated HeapSort가 더 수행시간이 빨라야하는데 백준 2751문제를 풀 경우 일반 HeapSort가 더빠르게 나옵니다. 해당 사항에 대해서는 더공부한후 알아봐야할것같습니다~~~~~

'Algorithm > 이론' 카테고리의 다른 글

MergeSort구현  (0) 2017.04.28
[백준] 2750 && Inplace QuickSort구현  (0) 2017.04.28
[백준] 2751번 문제 HeapSort구현  (0) 2017.04.27
[알고리즘] BinarySearch  (0) 2017.03.30