51. 힙 정렬

힙 정렬이란?

힙 정렬은 힙 자료구조를 기반으로 한 정렬 알고리즘이다. 힙은 완전 이진트리 형태로 구성되며, 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 트리이다. 힙 정렬은 주어진 리스트를 힙으로 변환한 후, 최대 힙 또는 최소 힙을 구성하여 정렬을 수행한다.

 

동작 방식

1. 주어진 리스트를 힙으로 변환한다. 이를 위해 최대 힙 또는 최소 힙으로 구성하는 고정을 수행한다.

2. 힙에서 최대(최소) 값을 추출하여 정렬된 리스트의 마지막 요소로 이동시킨다.

3. 힙의 크기가 1이 될 때까지 위 과정을 반복한다.

 

힙 정렬은 힙 자료구조를 사용하기 때문에 효율적인 정렬 알고리즘이다.

시간 복잡도는 항상 O(n log n)을 가진다. 하지만 일반적으로 다른 정렬 알고리즘보다는 느린 편에 속한다.

힙 정렬은 특히 정렬되지 않은 리스트를 한 번에 정렬해야 할 때 유용하며, 추가 메모리 공간을 요구하지 않는다.

---

#define SWAP(a,b,t) ((t=a), (a=b), (b=t))

// 히프 정렬 함수 
void HeapSort(int User_Data[], int n){
	int i, j, temp;
	int Heap[n+1];
	Max_Heap(User_Data, Heap, n, 1);
		
	// 랜덤으로 되어 있는 배열을 히프로 변경시킨다. 
	for(i=n/2; i>0; i--) adjust(Heap, i, n);
	
	// MAX HEAP 이므로 큰 값이 먼저 정렬된다. 
	// Heap 출력과 동일한 동작을 통해 큰값부터 정렬한다. 
	for(i=n-1; i>0; i--){
		SWAP(Heap[1], Heap[i+1], temp);
		adjust(Heap, 1, i);
	}
	
	Max_Heap(User_Data, Heap, n, 0);
}

// 히프 조정 함수 (현 배열을 히프로 만들기 위한 함수) 
void adjust(int User_Data[], int root, int n){
	int temp = User_Data[root];
	int child = 2 * root;
	
	while(child <= n){
		if((child < n) && (User_Data[child] < User_Data[child+1])) child++;
		if(temp > User_Data[child]) break;
		else{
			User_Data[child/2] = User_Data[child];
			child *= 2;
		}
	}
	User_Data[child/2] = temp;
}

// 일반 배열은 0번부터 이므로 Heap 연산을 위해 1번으로 옮기고 원상복구 시키는 함수 
void Max_Heap(int User_Data[], int Heap[], int n, int check){
	int i;
	if(check)
		for(i = 0; i<n; i++)
			Heap[i+1] = User_Data[i];
	else
		for(i = 0; i<n; i++)
			User_Data[i] = Heap[i+1];
}