개념 요약
- 완전 이진트리를 기본으로 하는 힙을 기반으로 한 정렬 방식
- 힙(Heap)
- 완전 이진트리의 일종으로 최댓값과 최솟값을 쉽게 추출할 수 있는 자료 구조
- 내림차순을 위함은 최대 힙, 오름차순을 위함은 최소 힙을 이용한다.
정렬 과정
- 절렬하기 위한 n개의 요소들로 최대 힙을 만든다.
- 루트에 최댓값이 있기 때문에 힙의 가장 마지막과 교체한다.
- 교체한 원소를 제외하고 다시 최대 힙을 만든다.
- 2번 3번의 연속.
코드
void swap(std::vector<int> &heap, int a, int b)
{
int temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
void heapify(std::vector<int> &heap, int n, int i)
{
// 부모, 왼쪽, 오른쪽 순으로 저장
int parent = i, l_c = i * 2 + 1, r_c = i * 2 + 2;
// 왼쪽 자식과 비교해서 인덱스 교환
if (l_c < n && heap[parent] < heap[l_c])
parent = l_c;
// 오른쪽 자식과 비교해서 인덱스 교환
if (r_c < n && heap[parent] < heap[r_c])
parent = r_c;
// 무언가 변환이 되었다면 교환후 재귀과정
if (i != parent)
{
swap(heap, parent, i);
heapify(heap, n, parent);
}
}
void heap_sort(std::vector<int> &unsorted_array)
{
int n = unsorted_array.size();
// 트리에 넣기.
for (int i = n / 2 - 1; i <= 0; --i)
heapify(unsorted_array, n, i);
// 최댓값을 뒤로 빼는 작업
for (int i = n - 1; i > 0; --i)
{
swap(unsorted_array, 0, i);
heapify(unsorted_array, i, 0);
}
}
시간 복잡도
- 평균, 최선, 최악의 경우 $O(nlogn)$
공간 복잡도
- 추가적 메모리 사용이 없기 때문에 $(On)$
장단점
- 효율적이며 가장 큰 값, 작은 값을 구하기에 용이하다.
- 같은 데이터 상태에 같은 시간 복잡도를 가진 정렬 방식보다 조금 느리다.