정렬 알고리즘(5. 힙 정렬)

힙 정렬

1. 개념

평균	최악	메모리	안정성
$O(N logN)$	$O(N logN)$	$O(1)$	X

힙 정렬은 말 그대로 힙을 사용하는 정렬 방식을 말합니다.
여기서 힙은
트리(tree)에 기반한 자료구조로 우선 순위 큐의 효율적인 구성 방식 중 하나입니다.

힙 정렬은 힙 자료구조를 사용해 최댓값 혹은 최솟값을 순차적으로 뽑으며 정렬하는 방식을 말합니다.

2. 동작 과정

1. 주어진 배열로 힙 자료구조를 만듭니다. → $O(N)$
2. 만들어진 힙 자료구조에서 루트 노드를 삭제하고 맨 뒤로 옮깁니다.
3. 해당 과정을 힙 자료구조가 빌때까지 반복합니다.

→ 최종적으로 정렬된 배열이 나옵니다.

3. 힙 정렬의 시간 복잡도

힙 정렬은 입력 배열을 힙 자료구조(완전 이진 트리)를 이용해 정렬하는 알고리즘입니다. 배열 자체를 힙 구조로 재구성한 후, 루트 노드를 반복적으로 삭제하며 정렬을 진행합니다.

힙을 구성하는데 배열의 모든 원소를 한 번씩 방문하여 제자리에서 힙의 속성을 만족하도록 재구성하기 때문에 보통 O(N)의 시간 복잡도를 가집니다.

또, 힙 자료구조가 완성된 상태에서 루트 노드를 삭제하고 다시 힙 자료구조를 재구성하는데 약 $O(logN)$ 만큼의 시간복잡도를 가집니다. 이런 작업을 모든 원소에 대해서 진행하기때문에 O(N)번 반복하게 됩니다.

이를 정리해보면 아래와 같습니다.

• 힙 구성: $O(N)$
• 루트 삭제 & 힙 재구성: $O(logN)$
• 삭제 & 힙 재구성 횟수: $O(N)$
• 시간 복잡도: $O(N) + O(NlogN)$ → $O(NlogN)$
• 공간복잡도: $O(1)$ → 배열 자체로 힙 자료구조를 만들기 때문
• 안정성: X

---