[Sorting] 힙 정렬, Heap Sort

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 힙 정렬 (Heap Sort)

• 최대 힙을 이용하여 루트를 힙의 가장 마지막 노드와 교환한 후 힙 크기를 1 감소시키고, 루트로부터 Downheap 연산을 통해 힙 속성을 복원하는 과정을 반복하여 정렬하는 알고리즘

Heap Sort, 출처 위키피디아

- 수행 시간

• 먼저 상향식(Bottom-up)으로 힙을 구성하는 데 O(n) 소요
• 루트와 힙의 마지막 노드를 교환한 후 Downheap을 수행하는 데에는 최대 힙의 높이, 즉 O(log(n)) 소요
• 루트와 힙의 마지막 노드를 교환하는 횟수는 n - 1
• 총 수행 시간은 O(n) + (n - 1) * O(log(n)), 즉 O(nlog(n))
• 힙 정렬은 어떠한 입력에도 항상 O(nlog(n))의 수행 시간 소요
• 루프 내 코드가 길고, 비효율적인 캐시 메모리 사용에 따라 대용량의 입력을 처리하기에는 부적절함