Heap Sort

Heap 정렬

최소힙을 구성하여 데이터를 넣고 빼는 작업을 하면 내림차순 정렬이 된다.( 빼면서 마지막 index에 뺀 값을 swap한다)

마찬가지로 최대힙은 위의 작업을 수행하면 오름차순 정렬이 된다.

테스트데이터는

1 2 10 0 7 6 3 11 8 4 순으로 넣었고 9가 입력되면 입력작업이 종료되게 하였다.

인풋이 들어가면서 힙 배열이 재정렬된다.

최종적으로 데이터 입력이 끝나면 하나씩 팝하면서 끝 데이터와 swap하면 내림차순 정렬이 되는것을 볼 수 있다.

https://github.com/ManSung-Kim/mantdu/blob/master/Algorithm/heap_sort.cpp

#include
#include
using namespace std;

#define NEXT_L(x) (((x)*(2))+(1))
#define NEXT_R(x) (((x)*(2))+(2))
int getParent(int a) {
	if(a%2==0) 
		return a/2-1;
	else
		return a/2;
}
void swap(int* a, int* b) {
	int* temp = b;
	*b = *a;
	*a = *temp;
}

typedef struct heap{
	int arr[100];
	int end;
	int popCnt;
	heap() {
		for(int i=0;i<100;i++) 
			arr[0] = 0;
		end = 0;
		popCnt=-1;
	}
	void put(int a) {
		int curr = end++;
		arr[curr] = a;
		while(1) {
			if(curr == 0 ) 
				break;
			int rParent = getParent(curr);
			if(arr[rParent]<=arr[curr]) {
				break;
			}			
			swap(arr[rParent], arr[curr]);
			curr = rParent;
		}
	}
	void pop() {
		if(popCnt==-1) { // init END IDX Cpy
			popCnt = end-1;
		}
		swap(arr[0],arr[popCnt]);
		int curr = 0;
		while(1) {
			int lChild = NEXT_L(curr);
			int rChild = NEXT_R(curr);
			int child = (arr[lChild]<=arr[rChild])?lChild:rChild;
			if(child>=popCnt
				|| arr[child] >= arr[curr]) 
				break;
			else {
				swap(arr[child], arr[curr]);
				curr = child;
			}				
		}
		popCnt--;
	}
}H;

int main() { H h;  int in; while(1) { cin &gt;&gt; in; if(in==9) // 입력종료로 9를 변수로 둠 break; h.put(in); // prt for(int i=0;i<h.end;i++)  cout<<h.arr[i]<<" "; cout<<endl; } while(1) { h.pop(); // 모든 팝이 수행되면 0~end까지 내림차순 정렬 완료 // prt for(int i=0;i<h.end;i++)  cout<<h.arr[i]<<" "; cout<<endl; if(h.popCnt==-1) break; } return 0; }