힙 정렬(Heap Sort Algorithm)

자료구조 '힙(Heap)'

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
• 자료구조 '힙(Heap)' 자세히 알아보기

 

힙 정렬(Heap Sort) 알고리즘의 개념 요약

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법
• 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

1. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
   - 내림차순을 기준으로 정렬
2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
3. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

내림차순 정렬을 위한 최대 힙의 구현

• 힙(Heap)은 1차원 배열로 쉽게 구현될 수 있다.
• 정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입한다.
• 최대 힙으로 구성된 배열에서 최댓값부터 삭제한다.

힙 정렬(Heap Sort) 알고리즘의 특징

• 시간 복잡도가 좋은편
• 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는것이 아니라 가장 큰 값 몇개만 필요할때이다.

---

원소들을 전부 힙에 삽입한다.
그리고 힙의 루트에 있는 값은 남은 수 들 중에서 최소값(최대힙이라면 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다.

 

이를 힙이 빌 때까지 반복한다.

 

 

기본적인 알고리즘은 선택 정렬과 동일하다.
하지만  힙 정렬의 경우 최소값, 최대값을 찾을때 배열을 순회하는게 아니라 만들어둔 힙을 사용하므로,
찾는데엔 O(logN) 그러므로 정렬에는 총 O(NlogN)의 시간복잡도를 갖게 된다.

 

힙 정렬은 추가적인 메모리를 전혀 필요로 하지 않는다.

또한 최악의 경우 O(N^2)의 성능을 내는 퀵 정렬과는 다르게 항상 일정한 성능을 발휘하므로 최소한의 알고리즘만 정의할 경우 힙정렬이 가장 안정적인 성능을 갖는다.