정렬4) 힙 정렬(Heap Sort)

* 힙 정렬
- 완전이진트리 를 기반으로 구현되는 정렬
- 이를 위해 배열의 index 0을 비워두고 1번부터 n까지 사용

- 왼쪽 자식의 노드 index = 부모 노드 index * 2
- 오른쪽 자식의 노드 index = 부모 노드 index * 2 + 1
- 왼쪽, 오른쪽 자식의 노드 index / 2 = 부모 노드 index


* 힙 정렬 로직
    1. 최대힙을 만든다
    2. Root Node와 가장 마지막 Node의 값을 Swap 한다
    3. n-1, n-2, ... n-1 까지 비교하여 Root Node에 있는 값을 다시 제자리로 보낸다.


* 시간 복잡도
    - 최대힙 완전 이진트리 구현 탐색 수: n - 1
    - 최대힙의 노드를 스왑하며 정렬 횟수: 2 * logn
    - O(nlogn)










* 힙 만드는 과정 등 까먹으면 출처가서 다시 보자
https://yabmoons.tistory.com/246?category=838490