힙 정렬(Heap Sort)

 

개념

힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.

 

어떤 리스트에 값을 넣었다가 빼내려고 할 때, 우선순위가 높은 것 부터 빼내려고 한다면 정렬을 떠올리게 된다. 하지만 정렬은 숫자가 낮을 수록 우선순위가 높다고 가정할 때 매 번 새 원소가 들어올 때 마다 이미 리스트에 존재하는 원소들과 비교를 해서 정렬을 해야한다. 이렇게 하면 비효율적이기 때문에 좀 더 효율이 좋게 만들기 위하여 힙은 다음과 같은 조건이 있다. '부모 노드는 항상 자식 노드보다 우선순위가 높다.' 즉, 모든 요소들을 고려하여 우선순위를 정할 필요 없이 부모 노드는 자식노드보다 항상 우선순위가 앞선다는 조건만 만족시키며 완전이진트리 형태로 채워나가는 것이다.

 

 

과정

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4. 2와 3을 반복한다.

 

예시

 

시간복잡도

평균 : Θ(nlogn)

최선 : Ω(nlogn)

최악 : O(nlogn)

 

 

 

 

 

 

 

 

 

 

 

---

 

참고 

https://gyoogle.dev/blog/algorithm/Heap%20Sort.html

https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC