최댓값을 꺼내는 구조
최대 힙은 부모의 값이 자식의 값보다 작지 않도록 유지하므로 루트에 최댓값이 놓인다. 매번 전체를 처음부터 훑어 최댓값을 찾는 대신 힙의 성질을 이용한다. 힙 전체가 정렬된 배열이라는 뜻은 아니다.
뒤쪽부터 확정
루트와 현재 힙의 마지막 원소를 교환하면 가장 큰 값이 뒤쪽 자리에 놓인다. 이 자리를 힙 범위에서 제외하고 바뀐 루트를 내려 보내며 힙 조건을 복구한다. 범위를 줄여 같은 작업을 반복한다.
시간과 공간
한 번의 복구는 힙의 높이에 비례하고 이를 여러 원소에 적용하여 최악 O(n log n) 시간이 든다. 표준적인 배열 기반 반복 구현은 같은 배열을 재사용하므로 추가 배열 없이 정렬할 수 있다.
같은 키의 순서
일반적인 힙 정렬은 같은 키를 가진 원소의 원래 순서를 보존하지 않는다. 따라서 성적 같은 기준값이 같을 때 입력 순서까지 유지해야 한다면 안정성 요구를 별도로 고려해야 한다.
관련 문서
힙 (자료 구조) / 배열 / 정렬 알고리즘 / 선택 정렬 / 시간 복잡도 / 이진 트리 / 우선순위 큐 / 병합 정렬