힙 정렬(heap sort)

• 힙(heap)을 사용하여 정렬하는 알고리즘
• 힙은 '부모 값 >= 자식 값' 라는 조건을 만족하는 완전이진트리이다.
  • 완전이진트리의 특징은 '완전이진' 상태이다.
  • 완전 : 부모는 자식을 왼쪽부터 추가하는 모양을 유지한다는 뜻
  • 이진 : 부모가 가질 수 있는 자식의 개수는 최대 2개라는 뜻
• 따라서 힙의 가장 위쪽에 있는 루트가 가장 큰 값이 된다.
• 힙은 형제의 대소 관계는 정해져 있기 않기 때문에 부분순서트리(partial ordered tree)라고도 한다.

힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 관계는 다음과 같다.

1. 부모는 a[(i - 1) / 2]
2. 왼쪽 자식은 a[i * 2 + 1]
3. 오른쪽 자식은 a[i * 2 + 2]

• 힙 정렬은 '가장 큰 값이 루트에 위치'한다는 특징을 이용하는 정렬 알고리즘이다.
• 힙 정렬은 선택 정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 큰 값을 구해야 한다. 
• 따라서 남은 요소에 대해 힙의 형태를 유지할 수 있도록 재구성해야 한다.

힙 상태 유지하기

1. 루트를 꺼낸다.
2. 마지막 요소를 루트로 이동한다.
3. 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸어 아래쪽으로 내려가는 작업을 반복한다. 이때 자식의 값이 작거나 앞에 다다르면 작업이 종료된다.

힙 정렬하기

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(1)로 줄일 수 있다.
  • 단순 선택 정렬은 정렬되지 않은 영역의 모든 요소를 대상으로 가장 큰 값을 선택한다.
  • 힙 정렬에서는 첫 요소로 가장 큰 값이 구해진다.
• 그 대신 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)이다.
  • 루트를 알맞은 위치로 내리는 작업은 이진 검색과 비슷해 스캔할 때마다 범위가 거의 반으로 줄어들기 때문
• 단순 선택 정렬은 전체 정렬에 걸리는 시간 복잡도는 O(n^2)이지만 힙 정렬은 힙으로 만드는 작업을 요소의 개수만큼 반복하므로 O(n log n)으로 크게 줄어든다.

//힙 정렬
 
//a[left] ~ a[right]를 힙으로 만든다 : 루트를 없애고 힙 상태 유지하기
static void downHeap(int[] a, int left, int right) {
    int temp = a[left];        //루트
    int child;                //큰 값을 가진 자식 노드
    int parent;                //부모
    
    for (parent = left; parent < (right + 1) / 2; parent = child) {
        int cl = parent * 2 + 1;        //왼쪽 자식
        int cr = cl + 1;                //오른쪽 자식
        child = (cr <= right && a[cr] > a[cl]) ? cr : cl;    //큰 값을 가진 자식 노드의 인덱스를 대입
        
        if (temp >= a[child])
            break;
        a[parent] = a[child];        //큰 값을 가진 자식 노드를 위로 올림
    }
    a[parent] = temp;
}
 
//힙 정렬
static void heapSort(int[] a, int n) {
    //초기 상태의 배열을 힙 상태로 만들기
    for (int i = (n - 1) / 2; i >= 0; i--) {    //a[i] ~ a[n - 1]를 힙으로 만들기
        downHeap(a, i, n - 1);
    }
    
    for (int i = n - 1; i > 0; i--) {
        swap(a, 0, i);                //가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
        downHeap(a, 0, i - 1);        //a[0] ~ a[i - 1]를 힙으로 만들기
    }
}