[알고리즘] 힙 정렬 알고리즘 (Heap Sort)

힙 정렬 (Heap Sort)

힙은 완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 찾아내기 위해 사용됩니다. 힙에는 최대 힙과 최소 힙이 존재합니다. 최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리이며 최소 힙은 자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리입니다.

 

힙 구조 생성과 최대 힙 연산에 관해서는 아래 포스팅에서 자세히 설명하였으니 참고하시기 바랍니다.

https://yjg-lab.tistory.com/143?category=932096 

[자료구조] 우선순위 큐 (priority queue), 히프의 삽입과 삭제

 

힙 생성(Heapify) 알고리즘이란 어떤 부모 노드의 두 자식 노드 중 크기가 더 큰 자식을 부모와 바꾸는 알고리즘입니다. 이러한 과정은 자식이 더이상 존재하지 않을 때까지 반복됩니다. 힙 정렬은 이러한 힙 생성 알고리즘을 사용하고 있습니다.

 

6   9   10   4   5   1   12   3

 

위와 같은 수가 있을 때 수들을 오름차순하는 힙 정렬을 해보겠습니다.

우선 완전 이진트리를 표현하기 위해 배열을 사용하여 데이터가 삽입되는 순서대로 배열의 인덱스를 정합니다.

 

인덱스 |  0   1    2   3   4   5    6    7 

데이터 |  6   9   10   4   5   1   12   3

데이터를 삽입한 배열을 완전 이진트리로 표현하면 위 그림과 같습니다.

표현된 트리를 힙 생성 알고리즘으로 최대 힙 구조로 만들면 위 그림과 같습니다.

이제 이 트리를 힙 정렬 해보겠습니다. 최상위 루트 노드와 말단 노드를 교환하고 다시 힙 구조로 재배열 하는 형식입니다.

12와 3을 교환하고 12의 정렬을 확정합니다. 확정된 12를 제외한 나머지 노드들을 다시 최대 힙 구조로 재배열합니다.

10과 6을 교환하고 10의 정렬을 확정합니다. 확정된 10를 제외한 나머지 노드들을 다시 최대 힙 구조로 재배열합니다.

9와 1을 교환하고 9의 정렬을 확정합니다. 확정된 9를 제외한 나머지 노드들을 다시 최대 힙 구조로 재배열합니다.

이러한 과정을 반복하면 트리의 리프 부분(배열의 뒷부분)이 오름차순으로 정렬되는 것을 확인할 수 있습니다.

 

알고리즘 구현

// Algorithm Analysis
// 힙 정렬 (Heap Sort) : 힙 구조를 사용하여 데이터를 정렬한다

#include <stdio.h>

int size = 8;
int heap[8] = { 6, 9, 10, 4, 5, 1, 12, 3 };

int main() {
	// 트리 구조를 최대 힙 구조로 변환
	for (int i = 1; i < size; i++) {
		int child = i;
		do {
			int root = (child - 1) / 2;
			if (heap[root] < heap[child]) {
				int temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			child = root;
		} while (child != 0);
	}
	// 힙 크기를 줄이면서 반복적으로 힙을 구성
	for (int i = size - 1; i >= 0; i--) {
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int child = 1;
		do {
			child = 2 * root + 1;
			// 자식 중 더 큰 값을 찾기
			if (heap[child] < heap[child + 1] && child < i - 1) {
				child++;
			}
			// root보다 자식이 더 크면 교환
			if (heap[root] < heap[child] && child < i) {
				int temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			root = child;
		} while (child < i);
	}
	for (int i = 0; i < size; i++)
		printf("%d ", heap[i]);

	return 0;
}

일반적으로 편의를 위해 힙 구조 배열의 0번째 인덱스를 인위적으로 비워놓고 1번째 인덱스를 시작 인덱스로 사용하는 힙 구조도 있습니다. 위 설명과 코드에서는 0번째 인덱스부터 데이터를 삽입합니다. 0번째 인덱스를 비워놓는 경우 그에 맞추어 코드를 수정하시면 됩니다.

 

전체 시간 복잡도 : O(N * logN)

힙 구조 생성시 연산 수는 힙의 높이와 동일하므로 O(log N)이 됩니다.

따라서 힙 정렬의 전체 시간 복잡도는 힙 생성(Heapify)알고리즘 시간 복잡도 O(log N) * 전체 데이터 수 N = O(N * logN)입니다. 

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.