Motivation

힙 정렬(Heap Sort)은 이진 힙(binary heap)을 사용하여 남아 있는 가장 큰 요소를 O(log n) 시간 내에 반복적으로 찾아내며, 신뢰할 수 있는 O(n log n) 정렬을 제공합니다.

힙 정렬을 배우는 이유는 무엇인가요?

• 보장된 O(n log n): 퀵 정렬(Quick Sort)과 달리, 최악의 경우에도 O(n²)이 발생하지 않습니다.
• 제자리 정렬(In-place): 병합 정렬(Merge Sort)과 달리 원래 배열 내부에서 정렬하며 O(1)의 추가 메모리만 필요합니다.
• 힙에 대한 직관: 힙이 배열에 저장되는 방식과 sift-down 연산이 힙의 유효성을 어떻게 유지하는지를 강화해 줍니다.

이 시리즈의 힙(Heap) 과정을 보셨다면, 힙 정렬은 해당 자료 구조를 정렬 알고리즘으로 활용한 것임을 알 수 있습니다.