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

힙

힙이란 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 힙은 최대값이나 최소값을 쉽게 구할 수 있다는 특징이 있다.

힙정렬

힙 정렬은 힙의 성질을 이용해 최대힙이나 최소 힙을 구성해 데이터를 정렬하는 방법이다.
내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

최대힙을 이용한 내림차순 정렬 구현법

1. 데이터 삽입

• 힙에 새로운 요소가 추가되면 마지막 노드에 이어서 삽입을 해준다.
  

삭제

힙정렬의 장단점

장점

• 추가적인 배열이 필요하지 않다.
• 시간복잡도가 항상 $O(nlogn)$로 보장된다.
• 이론상 퀵,병합 정렬보다 우위에 있다.
• max 또는 min 값을 구할 때 시간 복잡도는 O(1)이다.

단점

• 일반적으로 속도만 비교하자면 퀵정렬이 평균적으로 더 빠르다. (그래서 잘 사용하지는 않는 정렬 방식이다.)

시간복잡도

힙 트리의 전체 높이가 거의 $log₂n$(완전 이진 트리이므로)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 $log₂n$만큼 소요된다.
요소의 개수가 n개 이므로 전체적으로 $O(nlog₂n)$의 시간이 걸린다.
$T(n) = O(nlog₂n)$