6. 힙 정렬(Heap Sort)

# 힙 정렬

• 힙 정렬 : 선택 정렬을 응용한 알고리즘
• 병합정렬, 퀵정렬만큼 빠른 정렬 알고리즘
• 가장 큰 원소를 찾는데 최적화된 형태의 이진트리

 

# 힙 정렬의 원칙

• 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소의 크기보다 크다.
• 트리에서 가장 큰 원소는 항상 트리의 루트에 존재한다.
• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.
• 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

 

# 힙 정렬의 과정

• 마지막 노드(제일 아래 왼쪽 노드)의 부모 노드부터 시작하여 루트 노드와 비교 검색
• 정렬의 과정은 최댓값을 검증하여 정상적인 힙 구조인지 확인 아닌 경우 자식노드와 부모노드 변경

 

# 복잡도 분석

• 시간 복잡도 : O(log n)
• 작업 복잡도 : O(n * log n)

# 코드 구현