힙 정렬(Heap Sort)

---

시간복잡도

최선	평균	최악
nlogn	nlogn	nlogn

힙

• 완전 이진 트리

• 우선순위 큐에 활용

• 최댓값, 최솟값을 쉽게 추출

• 최소 힙

  • 부모 노드의 값이 자식 노드의 값보다 작거나 같음

  • 내림차순 정렬에 활용

• 최대 힙

  • 부모 노드의 값이 자식 노드의 값보다 크거나 같음

  • 오름차순 정렬에 활용

• 삽입할 때는 마지막 인덱스에 삽입 삭제할 때는 루트 노드 삭제

특징

• 시간복잡도가 좋다

  • 힙이 완전 이진 트리이기 때문에 높이는 logn이고 하나의 요소를 힙에 넣거나 뺄 때, logn의 시간 소요

  • nlogn

• 공간복잡도

  • n개의 요소를 담고 있는 배열 안에서도 가능

  • n

• 자료 전체가 아닌 가장 큰(작은) 값 몇 개를 구할 때 유용

• 불안정 정렬

알고리즘(오름차순)

• 힙의 루트 노드엔 항상 최대값이 있음을 활용

1. 최대 힙을 구성

2. 루트 노드와 마지막 노드와 교환

3. 마지막 노드 제거하여 배열의 뒤에 넣음

4. 1~3번 반복

• 출처