Algorithm - heap sort

heap sort란?

최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법입니다.

시간 복잡도는 n log(n) 입니다.

전체 소스 코드 : https://github.com/juwith/jsutilspp/blob/master/sort-heap/src/heapsort.cpp

Max heap - insert

아래와 같은 tree에 280을 추가한다고 가정해봅시다.

먼저 가장 끝 node에 index를 추가합니다.

새로운 노드와 부모노드를 비교하여 새로운 노드가 더 크다면 현재 노드를 부모노드랑 같은 값으로 만듭니다.

같은 과정을 최상위 노드까지 반복합니다.

최상위 노드까지 새로운 노드가 비교할 노드보다 크거나, 또는 새로운 노드가 부모노드보다 작다면 해당 노드를 새로운 노드로 설정합니다.

소스코드

	void insert(int x)
	{
		array.push_back(x);
		int target = array.size();
		while( target > 1 && x > array[(target/2)-1]) {
			array[target-1] = array[(target/2)-1];
			//cout << "target = " << target << ", target/2 = " << target/2 << endl;
			target /= 2;
			//cout << "target:" << target << endl;
		}
		//cout << "======end target========target:" << target << endl;
		array[target-1] = x;
	}

Max heap - pop max(delete)

max heap은 항상 최상위 노드가 최대값이므로 최상위 노드를 하나씩 pop한다면 max 정렬이 가능합니다.

먼저 최상위 노드를 제거하고, 가장 마지막에 있는 노드를 최상위로 만듭니다.

삽입한 노드의 자식노드 중 큰 노드와 삽입한 노드의 크기를 비교합니다.

삽입한 노드가 작다면 자식 노드 중 큰 노드를 부모노드로 만듭니다.

같은 과정을 자식노드가 없거나 이미 자식노드보다 큰 값일때까지 반복합니다.

소스코드

	int popMax()
	{
		//max is always first factor by heapify(insert)
		int max = array.front();

		//end factor moves to first factor
		array.front() = array.back();
		array.pop_back();

		//heapify
		int x = array.front();
		int parent=1, child=2;
		int arrSize = array.size();
		while(child <= arrSize) {
			if(array[child-1] < array[child]) {
				child++;
			}
			if(x >= array[child-1]) {
				break;
			}
			array[parent-1] = array[child-1];
			parent=child;
			child *= 2;
		}
		array[parent-1] = x;

		return max;
	}

Min heap

최소 힙은 최대 힙을 반대로 생각하면 됩니다. github 소스코드 예제에 올려놨으니 참고하시면 됩니다.

2D heap

아래 소스는 heap에 data형식을 달아 index, item으로 구현해놓은 소스입니다.

https://github.com/juwith/jsutilspp/blob/master/sort-heap-2d/src/heapsort2d.cpp