[Algorithm] 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

힙 정렬은 시간 복잡도가 O(NlogN)인 정렬으로, 버블 / 선택 / 삽입 정렬에 비해 우수한 성능을 가지고 있다.

 

우선 힙 정렬을 살펴보자.

힙은 자료구조 중 하나로, 이 'Heap' 자료구조의 특성을 활용한 정렬 방법이다.

힙은 완전 이진트리의 일종으로, 여러 값들 중에서 최솟값 혹은 최댓값을 빠르게 찾기 위해 설계된 자료구조이다.

힙은 느슨한 정렬 상태(반 정렬 상태)를 유지하고, 이를 쉽게 풀이하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.

부모 노드의 키 값이 자식 노드의 키 값보다 큰 지, 작은 지에 따라 힙의 종류가 나뉜다.

- 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 큰 힙 → 루트 노드에 가장 큰 원소가 위치하게 된다.

- 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작은 힙 → 루트 노드에 가장 작은 원소가 위치하게 된다.

 

 

힙 정렬의 알고리즘을 단순하게 나타내면 다음과 같다.

1. 정렬하고자 하는 배열을 힙으로 만든다. (이 과정을 heapify라고 한다.)
2. 정렬된 원소들이 저장될 새로운 배열을 생성한다. (이 배열을 정렬 배열이라 부르자.)
3. 힙의 루트노드의 값을 정렬 배열에 append하고, 루트 노드의 값을 삭제한다.
4. 삭제 한 후 나머지 트리에 대해서 다시 힙으로 만든다. (heapify)
5. 힙에 남은 원소가 하나도 없을 때까지 3~4번 과정을 반복한다.
6. 힙에 남은 원소가 없으면, 정렬 배열 속 원소들은 모두 정렬이 되어있다. (Min Heap의 경우 오름차순, Max Heap의 경우 내림차순으로 정렬이 된다.)

 

힙 정렬 파이썬 코드

 

 

힙 정렬 자바 코드

 

 

힙 정렬 장단점

장점

• 항상 O(NlogN)을 보장
• max 또는 min 값을 구할 때 시간 복잡도는 O(1)이다.

단점

• 일반적으로 속도만 비교하자면 퀵이 평균적으로 더 빠르다. 그래서 잘 사용하지 않음.