Heap Sort

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static class IntHeapSort {
        ArrayList<Integer> heap;
        int numberOfExchanges;
        int exchangeNumberCheck;
        ArrayList<Integer> snapshot;
        public IntHeapSort(int size, int checkNumber) {
            heap = new ArrayList<Integer>(size + 1);
            heap.add(0); // dummy
            exchangeNumberCheck = checkNumber;
        }
        private void buildMinHeap(ArrayList<Integer> heap, int size) {
            //    build_min_heap(A[], n) {
            //        for i <- ⌊n / 2⌋ downto 1
            //        heapify(A, i, n)
            //    }

            for (int i = (size / 2); i >= 1; --i) {
                heapify(heap, i, size);
            }
        }
        private void heapify(ArrayList<Integer> heap, int i, int size) {
            //# A[k]를 루트로 하는 트리를 최소 힙 성질을 만족하도록 수정한다.
            //# A[k]의 두 자식을 루트로 하는 서브 트리는 최소 힙 성질을 만족하고 있다.
            //            # n은 배열 A의 전체 크기이며 최대 인덱스를 나타낸다.
            //    heapify(A[], k, n) {
            //        left <- 2k; right <- 2k + 1;
            //        if (right ≤ n) then {
            //            if (A[left] < A[right]) then smaller <- left;
            //                                else smaller <- right;
            //        }
            //    else if (left ≤ n) then smaller <- left;
            //    else return;
            //
            //    # 최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수정한다.
            //        if (A[smaller] < A[k]) then {
            //            A[k] <-> A[smaller];
            //            heapify(A, smaller, n);
            //        }
            //    }

            int leftChild = 2 * i;
            int rightChild= 2 * i + 1;
            int smaller;
            if (rightChild <= size) {
                if (heap.get(leftChild) < heap.get(rightChild)) {
                    smaller = leftChild;
                } else {
                    smaller = rightChild;
                }
            } else if (leftChild <= size) {
                smaller = leftChild;
            } else return;

            if (heap.get(smaller) < heap.get(i)) {
                Integer temp = heap.get(i);
                heap.set(i, heap.get(smaller));
                heap.set(smaller, temp);

                numberOfExchanges++;
                if (numberOfExchanges >= exchangeNumberCheck) {
                    snapshot = new ArrayList<>(heap);
                    throw new RuntimeException("허용 교환 횟수 초과");
                }

                heapify(heap, smaller, size);
            }
        }
        public void heapSort() throws RuntimeException {
            //    heap_sort(A[1..n]) { # A[1..n]을 정렬한다.
            //        build_min_heap(A, n);
            //        for i <- n downto 2 {
            //            A[1] <-> A[i];  # 원소 교환
            //            heapify(A, 1, i - 1);
            //        }
            //    }

            int lastIdx = heap.size() - 1;
            buildMinHeap(heap, lastIdx);
            for (int i = lastIdx; i >= 2; --i) {
                Integer temp = heap.get(i);
                heap.set(i, heap.get(1));
                heap.set(1, temp);

                numberOfExchanges++;
                if (numberOfExchanges >= exchangeNumberCheck) {
                    snapshot = new ArrayList<>(heap);
                    throw new RuntimeException("허용 교환 횟수 초과");
                }

                heapify(heap, 1, i - 1);
            }
        }

        public int getNumberOfExchanges() {
            return numberOfExchanges;
        }

        public ArrayList<Integer> getSnapshot() {
            return snapshot;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        int numberOfElements = Integer.parseInt(st.nextToken());
        int exchangeNumberCheck = Integer.parseInt(st.nextToken());

        IntHeapSort intHeapSort = new IntHeapSort(numberOfElements, exchangeNumberCheck);

        st = new StringTokenizer(bf.readLine()," ");
        for(int i = 0 ; i < numberOfElements ; i++){
            intHeapSort.heap.add(Integer.parseInt(st.nextToken()));
        }
        bf.close();;

        boolean overflow = false;

        try {
            intHeapSort.heapSort();
        } catch (RuntimeException e) {
            overflow = true;
            ArrayList<Integer> snapshot = intHeapSort.getSnapshot();
            for (int i = 1; i <= snapshot.size() - 1 ; ++i) {
                bw.write(String.valueOf(snapshot.get(i)));
                bw.write(" ");
            }
        }

        if (!overflow) {
            bw.write("-1");
        }

        bw.flush();
        bw.close();
    }
}

문제 바로가기:
http://boj.kr/a466262188ea48a78c7f1c6635942ee5
썸네일 출처:
https://yuminlee2.medium.com/heap-sort-algorithm-6e200dc51845