2-(1) HeapSort

이 챕터는 2-(0)에서 알아본 Heap의 성질과 그 연산들을 통해 어떻게 효율적인 Sorting을 구현할 수 있는지 알아본다.

우선, 원래 있는 배열을 Heap으로 만든다. 이것이 2-(0)에서 말했듯이 BuildHeap과정인데, 이것이 n time걸리는 것을 저번 글에서 알아보았다. 이제 해야할 일은 계속 최대인 원소를 뽑는 것이다.

 

우선, 처음으로 만든 Heap을 생각해보자. 그러면 그 Heap에서 최대인 원소, 즉 배열의 맨 뒤로 가야할 원소는 현재 배열의 제일 첫번째 원소인 root node에 존재한다. 따라서 이 root node와 마지막 node를 swap해준다. 그 다음 마지막 노드는 더 이상 Heap의 일종으로 생각하지 않는다.

 

이러면 이제 바뀐 root입장에서 양 옆 tree는 Heap이지만 root가 두 childnode보다 더 작은 수가 될 수도 있으므로 전체적인 Heap은 깨졌다. 그러면 rootnode에 대해서 Heapify를 해주면 된다. 그럼 또 MaxHeap이 만들어진다. 이후 Heap에서 다시 첫 원소와 마지막 원소 교환, 마지막 원소는 힙에서 제외,, 이것을 root노드의 leftChild까지 반복해주면 뒤에서부터 정렬된 배열이 완성된다.

TestCode와 모든 필요함수를 포함한 코드는 다음과 같다.

#include<iostream>
#include<time.h>
#define INFINITE 1000000
using namespace std;
void swapPos(int& arr1,int& arr2) {
	int temp = arr1;
	arr1 = arr2;
	arr2 = temp;
}

void maxHeapify(int* arr,int size,int idx) {
	//역할은 그 노드와 left child, right child 를 비교하여 가장 큰 것을 위에 올리는 것.
	//idx is start point of Heapify
	int leftChild;
	int rightChild;
		//1-(i) Child가 없거나 하나인 경우
	if (2 * idx + 1 > size - 1) //leaf node인 경우
		return;
	else if (2 * idx + 1 == size - 1) //right child만 없는 경우(==leftChild가 배열의 마지막 원소인 경우)
	{
		leftChild = arr[2 * idx + 1];
		rightChild = -INFINITE;
	}
	else {
	//1 - (ii)Child가 다 있는 경우
		leftChild = arr[2 * idx + 1];
		rightChild = arr[2*idx+2];
	}


	//2-(i) parent node is biggest among 3 elements
	if (arr[idx] >= leftChild && arr[idx] >= rightChild)
		return; //Heapify를 밑의 원소들에 대해 할 이유가 없음
	else {//2 - (ii)parent node is smaller than child node
		if (leftChild >= arr[idx] && leftChild >= rightChild){ 
			//leftChild is biggest among 3 elements
			swapPos(arr[idx], arr[2 * idx + 1]);
			maxHeapify(arr, size, 2 * idx + 1);
		}
		else {
			//rigtChild is biggest among 3 elements
			swapPos(arr[idx], arr[2 * idx + 2]);
			maxHeapify(arr, size, 2 * idx + 2);
		}
	}

}


void Heapsort(int* arr, int size) {
	//(1) first, make Maxheap
	//(i) last index of array is size-1
	//if size-1 = 2n+2(even), last internal node is n, thus n = (size-3)/2
	//if size-1 = 2n+1(odd), last internal node is n, thus n = (size-2)/2
	int lastInternal = ((size - 1) % 2 == 0) ? (size - 3) / 2 : (size - 2) / 2;
	//now Build Heap
	for (int i = lastInternal; i >= 0; i--) {
		maxHeapify(arr, size,i);
	}
	//->now arr[0]is biggest element in array
	for (int i = 1; i < size; i++) {
		swapPos(arr[0], arr[size - i]);
		maxHeapify(arr, size- i, 0);
	}
}
void BuildHeap(int* arr, int size) {
	//(i) last index of array is size-1
	//if size-1 = 2n+2(even), last internal node is n, thus n = (size-3)/2
	//if size-1 = 2n+1(odd), last internal node is n, thus n = (size-2)/2
	int lastInternal = ((size - 1) % 2 == 0) ? (size - 3) / 2 : (size - 2) / 2;
	//now Build Heap
	for (int i = lastInternal; i >= 0; i--) {
		maxHeapify(arr, size, i);
	}
}
bool Issort(int*arr,int size) {
	for (int i = 0; i < size-1; i++) {
		if (arr[i] > arr[i + 1]) return false;
	}
	return true;
}

int main() {
	int arrsize;
	cout << "Enter size of array: ";
	cin >> arrsize;
	const int range = 10000;
	int* arr = new int[arrsize];
	double m_ratio = 0.5;	//Change the ratio of negative numbers
	srand((unsigned int)time(NULL));
	for (int i = 0; i < arrsize; i++)
	{
		arr[i] = rand() % range - int(m_ratio * range);
	}
	Heapsort(arr, arrsize);
	cout << Issort(arr, arrsize);

}

 

HeapSort의 시간 복잡도를 분석해보자.

우선 BuildHeap을 하므로 n 시간이 들고

노드가 j개 남았을 때 Heapify하는 시간은 h=logj이다.

따라서 다음과 같이 시간 복잡도를 계산해보면 된다.

아 몰라 1부터 n까지 더하면 nlogn이 상한이래,,ㅜㅜ