[알고리즘] 정렬 알고리즘 (2) (힙정렬)

1. 개념

: 비교 기반 정렬 알고리즘 중 하나로써 완전 이진 트리를 기반으로 하는 이진 힙의 속성을 이용해 리스트를 정렬하는

알고리즘.

최대 힙 or 최소 힙으로 구현할 수 있으며

최대 힙 => 오름차순

최소 힙 => 내림차순

으로 정렬할 수 있는 정렬 방식이다.

(공부할 때 '앞'에서부터 채워나간다고 해서 "최대 힙의 루트노드값이 먼저 할당되는데 왜 오름차순이지..?"라고 생각했었는데 여기서 '앞'에서 채워나간다는 말은 배열의 끝부터 채운다는 말이었다. == *0번 인덱스가 아닌 끝 인덱스부터 채움.*

혹시나 나처럼 헷갈려했던 사람이 있을까봐 작성한다 + 나중에 나도 까먹을까봐)

 

최대 힙을 사용한 오름차순 힙 정렬 (항상 배열의 뒤부터 채워나간다)

---

 

2. 정렬 과정

1) 주어진 리스트를 최대 힙 or 최소 힙으로 구성 => "힙 구성(Heapify) 단계" 

① 기준이 되는 현재 노드의 두 자식 노드끼리 크기를 비교하고 그 중에 큰 수를 기준 노드와 비교하여 클 경우 자리 교체(최대 힙 기준)

② 재귀과정을 통해 해당 과정을 반복하여 최대 힙 or 최소 힙을 구성

 

2) 힙에서 최대 힙이 정렬되었으면 루트 노드를 배열의 끝으로 이동 (최대 힙 기준)

 

3) 루트노드 자리에 우선순위가 가장 높은 노드가 (마지막 인덱스 == 제일 오른쪽 아래 노드) 루트 노드 자리에 위치함

 

4) 힙이 빌 때까지 위 과정 반복

---

 

3. 시간 복잡도

평균 시간복잡도 - O(n log n)

최악 시간복잡도 - O(n log n)

▶ 최악의 경우에도 O(n log n)을 보장하기 때문에 퀵 정렬보다 안정적이지만

캐시 비효율성(배열을 힙 형태로 유지하면서 데이터를 자주 교환하기 때문에 성능 Down)때문에 퀵 정렬보다 느릴 수 있음

---