특징 1. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬 3. 일반적으로 최고, 평균, 최악 시간 복잡도O(N * logN) 4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1) 알고리즘 힙(Heap) 자료구조를 이용하여 정렬한다. 힙은 마지막 depth를 제외하고 모든 노드가 왼쪽부터 채워져있는 완전 이진 트리 구조이며, 제일 큰 수나, 제일 작은 수를 빠르게 뽑아낼 수 있도록 하는 자료구조다. 최대힙은 트리의 노드 중 최댓값이 루트 노드에 존재하며, 최소힙은 트리의 노드 중 최솟값이 루트 노드에 존재한다. 힙정렬은 최대힙과 최소힙으로 모두 구현 가능하지만, 본 포스팅은 최대힙으로 진행한다. 완전 이진트리는 위와 같이 배열로 표현할 수 있다. 혹은 배열을 위와 같은 완전 이진 트리로..