힙 정렬은 힙에서 우선순위가 가장 높은 원소를 반복적으로 꺼내 정렬하는 방법이다.
원리
배열을 최대 힙으로 만든 뒤 루트의 최댓값을 마지막 미정렬 위치로 옮긴다. 힙 범위를 줄이고 조건을 복구하는 과정을 반복한다.
예시
최대 힙에서 가장 큰 원소를 뒤로 보내면 배열 끝에서부터 오름차순 결과가 확정된다.
주의할 점
전형적인 배열 구현은 최악 O(n log n), 추가 공간 O(1)이지만 안정적이지 않다. 같은 점근적 시간이라도 메모리 접근 패턴 때문에 다른 정렬과 실제 속도는 다르다.