힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

• 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다.
• 불안정 정렬에 속한다.

완전 이진 트리

• 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조이다.
• 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다.

과정

1. 최대 힙을 구성한다.
2. 현재 힙 루트는 가장 큰 값이 존재한다. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나를 줄인다.
3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다.

유용한 경우

• 가장 크거나 가장 작은 값을 구할 때
• 최대 k만큼 떨어진 요소들을 정렬할