[알고리즘]힙 정렬(Heap sort)

힙 정렬

힙 정렬은 힙 트리를 구성하여 내림 차순 정렬하는 방식을 말한다.

힙이란?
https://velog.io/@zoepark/%ED%9E%99Heap

힙 정렬 과정

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

힙 정렬의 장점
항상 O(nlogn)의 성능을 발휘