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

힙정렬이란?

• 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬방식
• 최댓값, 최솟값을 추출할 수 있는 자료구조
• 불안정 정렬
• 내림차순 정렬 => 최대 힙 / 오름차순 정렬 => 최소 힙
• 시간복잡도가 좋은편
• 가장 큰 값 몇개만 필요할 때 가장 효율적으로 사용 가능

완전 이진 트리란?
[삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리]

 

힙 정렬 과정

1. 최대 힙을 구성(내림차순 정렬 기준)
2. 힙에서 한개씩 요소를 꺼내 배열 뒤에 저장
3. 최대값부터 삭제하며 감소되는 순서로 정렬

 

시간 복잡도

최악	평균	최선
O(nlog₂n)	O(nlog₂n)	O(nlog₂n)

 

[참고 자료]

• 링크