[자료 구조][알고리즘] 히프정렬 (heap sort)
2018.12.10
히프정렬 (heap sort) 합병 정렬방식은 비록 최악의 경우 연산 시간과 평균 연산 시간 모두 O(nlogn)이지만, 정렬할 레코드 수에 비례하여 저장 공간이 추가로 필요하다. 히프 정렬(heap sort)은 일정한 양의 저장 공간만 추가적으로 필요한 동시에, 최악의 경우 평균 연산 시간이 O(n log n)이다. 하지만, 히프 정렬은 합병 정렬보다 약간 느리다. 히프 정렬의 핵심 알로리즘은 이름처럼 히프를 사용한다. 그중에서도 최대 히프 구조를 이용한다. 따라서, 최대 히프가 되도록 레코드를 재조정 후 루트를 하나씩 빼내면서 정렬을 하는 기법이다. 알로리즘을 정리하면, 1. 최대 히프 생성 2. 히프의 첫 번째 와 마지막 레코드 스와핑 3. 히프 크기 감소 및 재조정 4. n-1 반복 최대 히프 생..