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

힙 정렬

최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로, 

내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

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

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

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

- 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬방식이다.

- 힙은 1차원 배열로 쉽게 구현될 수 있다.

- 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값이나 작은 값을 구할 때, 최대 k만큼 떨어진 요소들을 정렬할 때 이다.

시간 복잡도

최선/최악/평균 모두 O(nlog n)

- 힙트리의 전체 높이가 거의 log2n(완전이진트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 log2n만큼 소요된다.

- 요소의 개수가 n개이므로 전체적으로 O(nlog2n)의 시간이 걸린다.