힙 정렬(Heap Sort)

개념 요약

• 완전 이진트리를 기본으로 하는 힙을 기반으로 한 정렬 방식
• 힙(Heap)
  • 완전 이진트리의 일종으로 최댓값과 최솟값을 쉽게 추출할 수 있는 자료 구조
• 내림차순을 위함은 최대 힙, 오름차순을 위함은 최소 힙을 이용한다.

---

정렬 과정

1. 절렬하기 위한 n개의 요소들로 최대 힙을 만든다.
2. 루트에 최댓값이 있기 때문에 힙의 가장 마지막과 교체한다.
3. 교체한 원소를 제외하고 다시 최대 힙을 만든다.
4. 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)$

---

장단점

• 효율적이며 가장 큰 값, 작은 값을 구하기에 용이하다.
• 같은 데이터 상태에 같은 시간 복잡도를 가진 정렬 방식보다 조금 느리다.