힙(Heap) 정렬

*힙(heap) 정렬 

선택 정렬을 응용한 알고리즘인 힙 정렬은 힙의 특성을 이용하여 정렬을 수행한다.
힙은 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리이다.
부모의 값이 자식보다 항상 작아도 힙이라고 한다.
힙은 형제의 대소관계가 정해져 있지 않아서 부분순서트리라고도 한다.

public class HeapSort {
    // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    //a[left] ~ a[right]를 힙으로 만듭니다.
    static void downHeap(int[] a, int left, int right) {
        int temp = a[left]; //root값
        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]) //root가 더 크다면 반복문 중지
                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]을 힙으로 만들기
        }
    }
}