정의 완전이진트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬 방식 동작 과정 1. 정렬할 N개의 원소로 최대 힙 구성 2. 최대 힙의 루트 노드와 마지막 원소 위치 교환 3. 새 루트 노드에 대해 최대 힙 구성 4. 원소 개수만큼 2와 3을 반복 수행 시간복잡도 최선일 경우 O(nlogn), 평균일 때 O(nlogn), 최악일 경우에도 O(nlogn)이다. 과정 1로 build heap 과정으로 O(nlogn)의 시간 복잡도를 가진다. 과정 2와 3은 최대 힙에서 원소를 하나 삭제한 다음 heapify를 진행하는 것과 같으므로 O(logn)이 걸리고 원소 개수만큼 반복되므로 O(nlogn)이 된다. 따라서 O(nlogn) + O(nlogn) = O(nlogn)의 시간복잡도를 가진다. 공간복잡도 추가적..
