[알고리즘] 힙 정렬 (Heap Sort)

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

힙정렬은 힙이라는 데이터 구조를 사용하는 것이 특정이다.

[자료구조] 힙 (Heap)

 

힙정렬

먼저 힙에 모든 숫자를 삽입한다. 힙은 내림차순이 되도록 구성한다.

내림차순 힙은 큰 값부터 순서대로 데이터를 꺼내는 성질이 있기 때문에 숫자를 역순으로 나열하면 정렬이 완료된다.

 

힙정렬

모든 숫자를 힙에 정렬했다. 힙에 저장된 숫자를 하나씩 꺼내 정렬한다.

 

힙정렬

먼저 뿌리에 있는 숫자 7을 꺼낸다.

 

힙정렬

그리고 다시 힙을 정렬한다.

힙정렬은 힙에 관한 포스팅( https://twd0622.tistory.com/20 )에 정리해뒀다.

 

힙정렬

다시 뿌리에 있는 6을 꺼내 7 옆에 정렬해 두고

 

힙정렬

다시 힙을 정렬해준다.

 

힙정렬

이런식으로 모든 데이터를 꺼낼 때까지 같은 작업을 반복한다.

 

힙정렬

모든 숫자를 힙에서 꺼내면 정렬이 완료된다.

---

📌 추가 내용

일반적으로 정렬할 수열은 배열로 주어진다. 이번에 예시로 힙이라는 데이터 구조를 사용했지만, 보통은 수열이 담긴 배열 자체에 힙을 끼워 넣어 배열상에서 숫자를 교체하며 정렬한다. 구체적으로는 힙의 각 요소와 배열 간에 다음과 같은 대응 관계를 만든다.

배열 (Array)

힙 (Heap)

⏱️ 시간복잡도

힙 정렬 초기에 n개 숫자를 힙에 삽입할 때 걸리는 시간은 O(n log n)이다. 이는 빈 상태에서 하나씩 데이터를 추가하면 되는데 힙의 높이는 log₂n 이하이므로 한 개 숫자를 추가하는데 O(log n)이 소요되기 때문이다.

 

그리고 각 라운드에서 최댓값을 추출한 뒤 힙을 재구축하는데 걸리는 시간은 O(log n)이다. 라운드 수는 n이므로 힙이 만들어진 뒤 정렬하는 시간 복잡도 O(n log n)이다. 따라서 힙 정렬의 전체 시간복잡도는 O(n log n)이다.

 

앞서 공부한 버블 정렬, 선택 정렬, 삽입정렬에 비해 속도가 빠르다. 하지만 힙이라는 복잡한 데이터 구조를 사용하기 때문에 구현에 어려움이 있다.

 

그래서 힙정렬이 가장 유용할 때는 전체 자료를 정렬하는 것 보다 특정 큰수 혹은 작은수 몇개만 필요할 떄 사용하면 좋다.

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠