Heap Sort

public class HeapSort {

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] A = {9, 4, 3, 8, 10, 2, 5};
        heapSort.sort(A);
        heapSort.printArray(A);
    }

    public void printArray(int[] A) {
        for (int num : A) {
            System.out.print(num + " ");
        }
    }

    public void sort(int[] A) {
        int n = A.length;

        // 힙 구성
        for (int i = n / 2 - 1; i >= 0; i--) {
            makeHeap(A, n, i);
        }

        // 힙에서 요소 하나씩 추출
        for (int i = n - 1; i > 0; i--) {
            // 현재 루트(최대값)를 끝으로 이동
            int temp = A[0];
            A[0] = A[i];
            A[i] = temp;

            // 감소된 힙에 대해 힙 속성 재구성
            makeHeap(A, i, 0);
        }
    }

    private void makeHeap(int[] array, int n, int i) {
        int root = i; // 루트
        int leftChild = 2 * i + 1; // 왼쪽 자식
        int rightChild = 2 * i + 2; // 오른쪽 자식

        // 왼쪽 자식이 루트보다 크면
        if (leftChild < n && array[leftChild] > array[root]) {
            root = leftChild;
        }

        // 오른쪽 자식이 현재 가장 큰 값보다 크면
        if (rightChild < n && array[rightChild] > array[root]) {
            root = rightChild;
        }

        // 가장 큰 값이 루트가 아니면 교환
        if (root != i) {
            int swap = array[i];
            array[i] = array[root];
            array[root] = swap;

            // 재귀적으로 힙 속성 재구성
            makeHeap(array, n, root);
        }
    }