[알고리즘] 힙 정렬(Heap Sort) [힙 트리를 활용한 정렬 알고리즘]

---

- 힙 정렬(Heap Sort)이란?

선택 정렬과 거의 같은 알고리즘으로,
가장 큰 원소를 뒤로 보내는 데에 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다.

- 힙 정렬의 정렬 과정

1. 원소들을 전부 힙에 삽입한다.
2. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다.
3. 힙이 빌 때까지 2의 과정을 반복한다.

힙 정렬(Heap Sort) 예시