힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

힙 자료구조를 이용하여 최대값(또는 최소값)을 반복 추출하며 정렬하는 알고리즘

목적: O(n log n) 보장, 제자리 정렬, 최악 케이스 안정

특징: 힙 기반, 불안정 정렬, 제자리, O(n log n) 보장

동작: ① 배열을 최대 힙으로 변환(Heapify, O(n)) → ② 루트(최대값)와 마지막 요소 교환 → ③ 힙 크기 감소 → ④ Heapify-Down → ⑤ 반복

Heapify: 배열을 힙으로 변환, Bottom-Up, O(n)

시간 복잡도: 최선·평균·최악 O(n log n) - 항상 일정

공간 복잡도: O(1) - 제자리

장점: O(n log n) 보장, 제자리, 최악 케이스 안정, 추가 메모리 없음

단점: 불안정, 평균적으로 퀵보다 느림, 캐시 비효율

적용사례: 최악 케이스 중요, 메모리 제약, Intro Sort 백업, 우선순위 큐

비교: 힙(보장/제자리/불안정/느림) vs 퀵(빠름/최악O(n²)) vs 병합(안정/O(n)공간)

연관: 힙, 우선순위 큐, Intro Sort, Heapify