힙 정렬(Heap Sort)은 대표적인 비교 정렬 알고리즘 중 하나로, 힙(heap) 자료구조를 이용하여 정렬하는 알고리즘입니다.
힙(heap)이란, 최대값 또는 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 형태의 자료구조입니다.
이진 트리이기 때문에 각 노드는 최대 2개의 자식 노드를 가지며, 왼쪽 자식부터 채워지는 구조를 가집니다.
**최대 힙(max heap)**은 부모 노드가 자식 노드보다 항상 큰 값을 가지는 구조이고, **최소 힙(min heap)**은 그 반대의 구조를 가집니다.
힙 정렬은 먼저 정렬되지 않은 리스트를 최대 힙 구조로 만듭니다. 이 때, 리스트를 트리 형태로 생각하고, 부모 노드와 자식 노드간의 크기 비교를 통해 최대 힙 구조를 만들어 갑니다. 이후 최대 힙의 최상위 노드(=최대값)를 제거하고, 힙의 특성을 유지하면서 다시 최대 힙을 구성합니다. 이 과정을 반복하면서 제거된 노드를 리스트에 추가하여 정렬된 리스트를 만듭니다.
힙 정렬의 시간복잡도는 최악, 최선, 평균 모두 **O(nlogn)**으로 매우 빠른 알고리즘이지만, 추가적인 메모리 공간을 필요로 하는 단점이 있습니다. 또한, 안정성을 보장하지 않습니다.
