목차 정렬 히프 정렬 Heap Sort 히프 정렬은 히프 자료구조를 이용하여 정렬하는 방법이다. 히프에서는 항상 가 장 큰 원소가 루트 노드가 되고. 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하는 특징이 있다. 그러므로 최대 히프에 대해서 원소 개수만큼 삭제 연산을 수행하면 내림차순으로 정렬된 원소를 얻을 수 있고, 최소 히프에 대해서 원소 개수만큼 삭제 연산을 수행하면 오름차순으로 정렬된 원소를 얻을 수 있다. 히프 정렬은 정렬할 원소들을 하나씩 히프에 삽입하여 정렬할 n개의 원소를 가진 최대 히프를 구성한다. 히프에 삭제 연산을 수행하여 얻은 루트 원소를 저장하고, 히프를 다시 최대 히프가 되도록 재구성하는 작업을 원소의 개수만큼 반복하면 정렬을 완성할 수 있다. 2023.11.20..