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

[정렬 알고리즘]

1. 선택 정렬

2. 버블 정렬

3. 병합 정렬

4. 퀵정렬

5. 힙정렬

6. Counting Sort

_________________________________

🔎힙 정렬 알고리즘

배열의 원소들을 힙에 넣고 루트 노드를 반복적으로 빼서 배열을 정렬하는 방식이다.

 

🔎힙

: 자료 구조 중의 하나로, 리프노드를 제외하고는 완전 이진 트리이고 왼쪽부터 값이 채워진 경우를 말한다. 부모 노드와 자식 노드의 값 관계에 따라 두가지로 나뉜다.

 

📌 최소힙

최소힙이란 [자식 노드의 값 > 부모 노드의 값] 이 모든 노드에 성립하는 힙이다. 이 때 루트노드는 모든 노드 값 중 최솟값을 가지게 된다.

 

📌 최대힙

최대힙은 반대로 [자식 노드의 값 < 부모 노드의 값] 이 모든 노드에 성립하는 힙이다. 이 때 루트노드는 모든 노드 값 중 최댓값을 가지게 된다.

 

🔎힙 정렬 알고리즘

1. 최대 힙을 만든다.

2. 루트 노드(최댓값)와 가장 작은 수를 교환한다.

3. 아까 교환한 루트 노드를 제외하고 1과 2를 반복한다.

🔎장점

$O(nlogn)$ 알고리즘 중에서 유일하게 Extra memory가 필요없는 제자리 정렬이다.

언제나 $O(nlogn)$ 시간이 걸린다.

 

🔎단점

$O(nlogn)$ 알고리즘 중에서 제일 느리다.(불필요한 swap)

정렬이 되어 있는 배열이 들어와도 $O(nlogn)$ 시간이 걸린다.

 

_______________________________________

 

📌 시간복잡도

$O(nlogn)$

 : 힙의 깊이가 거의 $logn$이 되고, 삽입과 삭제에 $logn$ 정도가 걸린다.

 : 삽입과 삭제를 n번씩 하기 때문에 힙정렬의 시간복잡도는 $O(nlogn)$

 : 실제 시간은 퀵정렬보다 느리다는데, 이유는 잘 모르겠다.

 

📌 공간복잡도

$O(n)$