힙 정렬 (Heap Sort)

Heap을 이용해 정렬을 하는 방법

힙 정렬을 위해서는 사전에 완전 이진 트리를 힙으로 만들고, 정렬을 수행할 수 있습니다. 위에서 만든 힙을 통해 정렬을 하는 방법을 구현합니다.
힙 정렬은 간단하게, 아래의 정렬하는 순서를 가지고있습니다.

최상위 노드 A와 가장 끝의 노드 B를 바꾼다.
바꿔진 A는 맨뒤로 가며,힙에서 제외한다.
바꾼 값 B는, 자신의 자식이 있다면, 두개를 비교하여 가장 큰 값과 맞 바꾼다.
3.의 내용을 힙이될때까지 반복한다.

정렬을 할 때는 Heap의 우선값을 이용해 진행하기 때문에 최대 힙 으로는 오름차순 정렬, 최소 힙으로는 내림차순 정렬을 할 수 있다.

가장 우선순위가 높은 값을 뒤로 이동시키고 다시 루트노드부터 힙을 만든다. 이 때 노드의 범위에서 정렬된 개수 만큼만 제외한다.

이 과정에서 제외된 범위는 오름차순으로 점점 정렬되는 것을 볼 수 있다.

정렬되는 요소가 많을 수 록 힙을 만드들기 위해 탐색하는 시간 또한 줄어든다.

구현 코드 (Java)

//== 노드와 그 자식중에서 더큰(또는 작은) 위치를 찾는 메소드 ==//
public static int findLargest(int arr[], int node, int eh) {
    // first child
    int fc = (2 * (node + 1)) - 1;

    if (fc + 1 < eh) {
        if (arr[fc] <= arr[fc + 1]) {
            return arr[fc + 1] <= arr[node] ? node : fc + 1;
        } else {
            return arr[fc] <= arr[node] ? node : fc;
        }
    }
    if (fc < eh && arr[node] < arr[fc]) {
        return fc;
    } else {
        return node;
    }
}

메인 함수

public static void sort(int [] heap) throws Exception {
    Heap.sort(arr);
}