힙 정렬(Heap Sort)

• 힙(Heap)

부모의 값이 자식의 값보다 항상 크다(또는 작다)는 조건을 만족하는 완전이진트리

 

트리의 레벨 순서대로 배열에 저장하면 a[i] 노드에 대하여 다음과 같은 관계가 성립:

1. 부모는 a[(i-1) / 2]

2. 왼쪽 자식은 a[i*2 +1]

3. 오른쪽 자식은 a[i*2 +2]

 

• 힙 정렬(Heap sort)

가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘

-> 힙에서 루트를 없앤 다음 다시 힙을 만들어야 함

 

1. 마지막 요소를 루트와 바꿈

2. 큰 값을 가지는 자식과 위치를 바꾸며 내려가는 작업을 정렬되지 않은 부분에서 반복.

자식이 더 작거나 leaf에 도달하면 종료.

 

static void downheap(int a[], int left, int right) { //힙을 만드는 함수(left ~ right)
	int temp = a[left]; //힙으로 정렬할 값
	int child;
	int parent;
	for (parent = left; parent < (right + 1) / 2; parent = child) { //4. 자식노드로 이동 - 자식 노드가 자식이 없으면 6. 자식이 있으면 계속 반복
		int cl = parent * 2 + 1; //왼쪽 자식
		int cr = cl + 1; //오른쪽 자식
		child = (cr <= right && a[cr] > a[cl]) ? cr : cl; //더 큰 값을 가진 자식
		if (temp >= a[child]) break; //1. 맨 처음 값이 더 크면 멈춘 뒤
		a[parent] = a[child]; //3. 맨 처음 값이 작으면 비교했던 자식을 부모로 올림
	}
	a[parent] = temp; //2. 멈춘 자리의 부모 노드로 들어감 5. 맨 처음 값을 해당 자리에 저장
}

void heapsort(int a[], int n) {
	int i;
	for (i = (n - 1) / 2; i >= 0; i--) //자식이 있는 마지막 부모 노드~루트 순서
		downheap(a, i, n - 1);
	for (i = n - 1; i > 0; i--) {
		swap(a[0], a[i]);
		downheap(a, 0, i - 1); //루트로 올라온 마지막 값의 자리를 다시 찾아서 저장해 줌
	}
}

 

시간 복잡도: O(n log n) - best, avg, worst