[TIL] 힙 정렬 Heap Sort

힙 정렬 Heap Sort

힙의 특성을 이용하여 정렬하는 알고리즘

힙은 '부모의 값이 자식보다 항상 크다'는 조건을 만족하는 완전 이진 트리

이 때 부모의 값이 항상 자식보다 작을 때도 힙을 만족한다

즉, 이러한 자식 부모 사이의 대소 관계가 일정하면 힙이다 

* 힙 Heap - 쌓아 놓음, 쌓아 놓은 더미 

 

힙에서 부모와 자식 간의 관계는 일정하지만, 형제 사이의 대소 관계는 일정하지 않으므로

부분 순서 트리 Partial Ordered Tree 라고 한다 

 

힙 정렬의 특징 

힙 정렬은 '힙에서 최대값은 루트에 위치한다'는 특징을 이용하여 정렬하는 알고리즘이다 

- 힙에서 최대값인 루트를 꺼낸다 
- 루트 이외의 부분을 힙으로 만든다 

 

이 과정에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다 

루트를 삭제한 힙의 재구성

1. 루트를 꺼낸다
2. 마지막 원소 (가장 하단의 오른쪽에 위치한 원소) 를 루트로 이동한다 
3. 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다
  자식의 값이 작거나 리프의 위치에 도달하면 이동을 종료한다 (*리프 Leaf - 트리에서 자식이 없는 노드)

힙 정렬 알고리즘 알아보기 

1. i 값을 n-1 로 초기화한다

2. a[0] 과 a[i] 를 교환한다

3. a[0], a[1], ..., a[i-1] 을 힙으로 만든다

4. i 값을 1씩 감소시켜 0 이 되면 종료한다 (그렇지 않다면 2로 돌아간다)

배열을 힙으로 만들기 

가장 아랫부분의 서브트리부터 상향식 Bottom-up 으로 진행하여 전체 배열을 힙으로 만든다 

 

힙 정렬의 시간 복잡도

단순 선택 정렬은 정렬되지 않은 부분의 모든 원소 중에서 최대값을 선택해야 하고,

힙 정렬은 맨 앞의 원소를 꺼내는 것만으로 최대값을 구할 수 있지만 남은 원소를 힙으로 재구성해야 한다 

 

단순 선택 정렬에서 최대값인 원소를 선택하는 시간 복잡도는 O(n) 이지만

힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n) 이다 

 

따라서 단순 선택 정렬의 시간 복잡도는 O(n^2) 이지만 (전체 비교 횟수가 n(n-1) / 2) 

힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는 데 걸리는 시간 복잡도는 O(n) + n⋅O(logn)= O(n logn) 이다