[정렬 알고리즘][파이썬] 힙 정렬

힙 정렬(heap sort)은 힙이라는 데이터 구조를 사용하는 것이 특징입니다. -책 알고리즘 도감

 

 

1. 힙에 숫자를 저장

 

 

처음에는 힙에 모든 숫자를 저장합니다. 그리고 힙을 내림차순 혹은 오름차순으로 구축합니다. 여기서는 내림차순으로 구축해보겠습니다.(내림차순 힙은 큰 것부터 순서대로 데이터를 추출하는 성질이 있으므로 꺼낸 숫자를 역순으로 나열하면 정렬이 완료됩니다. 반대로 오름차순 힙은 꺼낸 숫자를 그냥 나열하면 정렬이 완료될 것입니다.)

 

 

 

2. '꺼내고 재구축' 반복

 

꺼내고 재구축1

힙에 저장된 숫자를 하나씩 '꺼내고 재구축'하는 것을 반복해주면 정렬이 완료됩니다. (재구축을 하는 방법은 '[자료 구조] 힙'을 참고하세요.)

 

 

 

꺼내고 재구축2

 

 

 

 

---

 

 

 

 

정렬 완료

 

 

<해설>

힙 정렬을 위해 n개의 숫자를 저장할 때 걸리는 시간은 O(n log n)이 됩니다. 빈 상태에서 데이터를 하나씩 추가하면 되지만, 힙의 높이가 log2n 이하이므로 1회 추가에 O(log n)의 시간이 걸리기 때문입니다. 또한, 각 라운드에서 최대 숫자를 꺼내서 힙을 재구축하는 데 걸리는 시간은 O(log n)입니다. 라운드 수는 n이므로 힙이 완성된 후에 정렬하는 시간도 O(n log n)이 됩니다. 따라서 힙 정렬의 계산 시간은 전체적으로 O(n log n)이 됩니다.

이것은 앞서 본 버블 정렬, 선택 정렬, 삽입 정렬의 O(n제곱)에 비해 빠른 속도입니다. 단, 힙이라는 복잡한 자료 구조를 구현하는 것이 어렵습니다.

 

 

참고 - 책 알고리즘 도감