완전 이진 트리의 일종인 힙(Heap) 자료구조를 기반으로 한 정렬 방식

최대 힙 트리나, 최소 힙 트리를 구성해 정렬하는 방법이다.

내림차순 정렬은 최대 힙을, 오름차순 정렬은 최소 힙을 구성하여 진행하면 된다.

불안정 정렬에 속한다.

🙄 힙, 힙트리가 뭐였더라…

<aside> 🤔 안정 정렬 vs 불안정 정렬

**안정 정렬**은 중복된 값을 입력 순서와 동일하게 정렬하는 방식. = 기존의 정렬 형태를 유지한 상태에서 정렬을 한다는 의미이다.

**불안정 정렬**은 중복된 값을 입력 순서와 상관 없이 무작위로 뒤섞인 상태에서 정렬한다.

• 예시 </aside>

💨 진행 과정(최대 힙) 💨💨💨

최대 힙을 구현한 뒤 루트 노드를 삭제하고, 다시 힙을 재구조화하는 과정을 반복해 정렬을 구현할 수 있다.

삽입보다는 삭제 과정만 이루어진다고 생각하는 것이 편하다고 하네요…

1. 정렬할 n개의 요소들로 이루어진 최대 힙(완전 이진 트리 형태)을 만든다.
2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내 배열의 뒤부터 저장한다.
3. 삭제되는 요소들(최댓값)은 값이 감소되는 순서로 정렬되게 된다.

⏰ 힙 정렬의 시간복잡도

시간복잡도가 굉장히 안정적이고 좋은 편

• 힙 트리의 전체 높이가 거의 log₂n(완전 이진 트리이므로)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 log₂n만큼 소요된다.
• 요소의 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 걸린다.

❓ 힙 정렬은 언제 쓰면 좋을까