정렬 알고리즘(Sort Algorithm) (7) - 힙 정렬(Heap Sort)

상위 글 : 정렬 알고리즘(Sort Algorithm)
1. 힙 정렬(Heap Sort)?
힙 정렬은 우선 순위 큐인 힙을 이용하여, 모든 원소를 힙에 집어넣었다가 빼는 방식으로 정렬을 하는 알고리즘 입니다.

1.1 힙이란?
이진 트리 형태로 윗쪽의 원소들이 아래쪽의 원소보다 작은 형태(Min Heap의 경우)로 저장하는 자료구조이다.

(이진 트리)

(Min Heap의 예 : 뿌리 1을 중심으로 아래쪽의 원소들은 위쪽의 원소보다 작다)

※ 이 글에서는 Min Heap을 기준으로 설명합니다.

1.2 힙에 원소를 추가하기
힙에 원소를 추가할 때는 가장 말단에 원소를 추가한 뒤 위쪽의 원소와 비교하면서 그보다 작을 경우 교환을 위쪽의 원소가 작은 경우나 뿌리에 도달할 때까지 반복하는 과정을 통해 원소를 추가하게 된다. 트리의 높이는 log N이므로 시간복잡도는 O(log N)이 된다.

1.3 힙에서 원소를 꺼내기
힙에 원소를 꺼낼 때에는 뿌리의 원소를 꺼낸 후 힙의 구조를 유지하기 위해 가장 말단의 원소를 뿌리로 옮긴 후 아래노드와 비교하여 자신이 작을 경우 교환하게 됩니다. 최악의 경우 트리의 가장 아래로 이동하게 되고, 트리의 높이는 log N이므로 시간복잡도는 O(log N)이 됩니다.

2. C를 이용한 구현