힙 정렬(heap sort)은 힙이라는 데이터 구조를 사용하는 것이 특징입니다. -책 알고리즘 도감 1. 힙에 숫자를 저장 처음에는 힙에 모든 숫자를 저장합니다. 그리고 힙을 내림차순 혹은 오름차순으로 구축합니다. 여기서는 내림차순으로 구축해보겠습니다.(내림차순 힙은 큰 것부터 순서대로 데이터를 추출하는 성질이 있으므로 꺼낸 숫자를 역순으로 나열하면 정렬이 완료됩니다. 반대로 오름차순 힙은 꺼낸 숫자를 그냥 나열하면 정렬이 완료될 것입니다.) 2. '꺼내고 재구축' 반복 힙에 저장된 숫자를 하나씩 '꺼내고 재구축'하는 것을 반복해주면 정렬이 완료됩니다. (재구축을 하는 방법은 '[자료 구조] 힙'을 참고하세요.) 힙 정렬을 위해 n개의 숫자를 저장할 때 걸리는 시간은 O(n log n)이 됩니다. 빈 상..