힙 정렬

heap : 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리.

 

최대 힙 : 부모 노드가 자식 노드의 값보다 더 큰 힙 (최소 힙은 이와 반대)

 

힙 정렬(오름차순 기준)을 하기 위하여 힙 구조를 가지도록 만들어야 하며, 최대 힙이 아닌 경우 힙 생성 알고리즘을 통해 부모 노드와 부모 노드보다 더 큰 값을 가지는 자식노드를 바꿔주는 과정을 거친다.

 

 

Heapify algorithm : 특정 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘

 

<힙 정렬의 과정>

1. 처음에 최대 힙 구조를 만든다.
2. 루트 노드와 마지막 원소를 바꿔준 후 집합의 크기를 감소시킨다.
3. 가장 큰 값이 마지막 원소로 바뀌면서, 이 원소를 제외하고 다시 힙 구조를 형성하여 2, 3번의 과정이 반복되면 마지막에 힙 정렬이 이루어진다.

 

시간복잡도: O(n*log n)

힙을 만들 때 높이만큼만 계산하면 되므로 log n에 비례하는 시간이 걸린다. 즉, heapify algorithm 의 시간 복잡도는 O(log n)이기때문에 이를 총 원소의 개수 n만큼 반복해서 수행하면 정렬이 이루어지므로 시간복잡도는 O(n*log n)이다.

 

장점: 병합 정렬과 달리 별도로 추가적인 배열이 필요하지 않으므로 메모리 측면에서 효율적이고 항상 O(n*log n)을 보장한다.

 

#include <stdio.h>

int n = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};

int main() {
	// 전체 트리 구조를 최대 힙 구조로 변경 
	for(int i = 1; i<n; i++) {  
		int c = i;
		do {
			int root = (c-1)/2;
			if(heap[root]<heap[c]) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			c = root; 
		}while(c!=0);
	}

	// 크기를 줄여가며 반복적으로 힙을 구성
	for(int i = n-1; i>=0; i--) {
		int temp = heap[0]; // 가장 큰 값을 가지는 루트 노드와 마지막 노드 교체 
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int c = 1;
		do { // 다시 최대 힙 구조를 만듦. 
			c = 2*root + 1;

			// 자식 중에 더 큰값을 찾기 
			if(heap[c]<heap[c+1] && c < i - 1) {
				c++;
			}

			// 루트보다 자식이 더 크다면 교환
			if(heap[root] < heap[c] && c < i) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			root = c; 
		}while(c<i);
	} 

	for(int i = 0; i<n; i++) {
		printf("%d ",heap[i]);
	}
}