힙 정렬

힙 정렬은 병합 정렬, 퀵 정렬만큼 빠른 정렬 알고리즘이다. 힙 정렬은 힙 트리 구조를 이용해서 정렬하는 방법이다. 힙은 완전 이진 트리를 기반으로 하며, 최솟값과 최댓값을 빠르게 찾아낼 수 있다

 

힙 정렬의 시간 복잡도 계산

1) 주어진 배열을 최대힙 혹은 최소힙으로 만든다 NlgN

2) 삭제를 통해서 정렬을 한다, 루트 노드에 관해서만 heapify를 하면 되기 때문에(이미 루트 빼고는 heapify를 유지하고 있다) lgN이 걸리고 N개를 정렬하는 것이기 때문에 NlgN이 걸린다

 

두 개의 사건을 독립적이기 때문에 실제 시간 복잡도는 O(NlgN)이라고 할 수 있다