힙 정렬 (Heap Sort) 이란?

힙 정렬이란?

자료구조 힙(heap)을 구성하여 정렬하는 방법이다.

힙이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이며 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조 이다.

이진트리란? 컴퓨터 안에서 데이터를 표현할 때 데이터를 각(Node)에 담은 뒤 노드를 두 개씩 이어 붙이는 구조이다.

 

최대 힙트리나 최소 힙트리를 구성해서 정렬하는 방법이다. 

내림차순 -> 최대 힙(부모노드가 자식 노드보다 큰 힙)으로 구성

오름차순 -> 최소 힙(자식노드가 부모노드보다 큰 힙)으로 구성

https://st-lab.tistory.com/225

 

1. 정렬해야할 N 개의 요소들로 최대힙(완전 이진트리 형태)를 만든다.   *최대힙이니, 내림차순 기준

2. 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.

3. 삭제되는 요소들(최대값부터 삭제)은 값이 감소되는 손서로 정렬되게 된다.

 

https://st-lab.tistory.com/225

 

힙 정렬 장단점은 ?

장점은 추가적인 배열이 필요하지 않는다는 점에서 메모리 측면에서 효율적이다.

또한 항상 O(nlogN) 이라는 시간복잡도를 보장할 수 있다는 점에서 빠른 정렬 알고리즘이다.

이론적으로는 퀵, 병합보다는 더 우위에 있다고 할 수 있다.

하지만 속도만 가지고 비교하면 퀵이 평균적으로 더 빠르기 때문에 힙 정렬은 일반적으로 사용되진 않는다.

 

시간복잡도는 ?

최대힙을 만드는 과정 => O(n)

DownHeap 과정 => O(2logN)

따라서, O(2nlogN + n) => O(nlogN) 이다. 또한 최악의 경우도 동일하다.