[자료구조] 히프 정렬(heap sort)...

히프 정렬은 히프 자료구조를 이용하여 정렬하는 방법이다. 히프에서는 항상 가장 큰 원소가 루트 노드가 되고, 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하는 성질이 있다. 그러므로 최대 히프에 대해서 원소의 개수만큼 삭제 연산을 수행하면 내림차순으로 정렬된 원소를 얻을 수 있다. 
 
 히프 정렬은 정렬할 원소들을 입력하여 최대 히프를 구성한다. 그리고 히프에 대해서 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치하고 히프를 다시 최대 히프가 되도록 재구성하는 작업을 원소의 개수만큼 반복하면 오름차순의 정렬을 완성할 수 있다.

 히프에 삭제 연산을 반복 수행하여 오름차순의 정렬된 원소를 구하기는 쉽지만, 삭제 연산을 수행한 후에 히프를 재구성하는 연산 수행 시간이 필요하다. n개의 노드에 대해서 완전 이진 트리는 log₂(n+1)의 레벨을 가지므로 완전 이진 트리를 히프로 구성하는 평균 시간은 O(log₂n) 이 된다. 따라서 n개의 노드에 대해서 히프의 평균 재구성 시간은 O(nlog₂n)가 된다.  

아래의 동영상을 참고하면 이해가 편하다.