[java] 백준 알고리즘 2751번 수 정렬하기2 풀이

힙정렬을 이용해서 풀었다.

힙정렬의 개념을 처음봐서 위키피디아와 다른 분들의 소스를 참고해서 풀었다.

위키피디아 링크: 힙정렬

힙정렬에 대해 정리를 잘해둔 블로그(그림 많아서 좋았음): 링크

공부가 돼서 좋았던 문제.

위의 링크에 파이썬으로 구현된 코드를 자바로 옮기듯이 구현했기 때문에

문제풀이는 링크 설명을 보는게 더 유용할 듯 싶다.

* 풀이 소스

public class baekjoon2751 {

    static StringTokenizer st;
    static int[] heapSort;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        heapSort = new int[N];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int input = Integer.parseInt(st.nextToken());
            heapSort[i] = input;
        }

        buildMaxHeap();

        for(int output: heapSort) {
            bw.write(String.valueOf(output));
            bw.newLine();
        }
        bw.flush();
    }

    public static void buildMaxHeap() {

        if(heapSort == null || heapSort.length < 1) {
            return;
        }

        for(int i= heapSort.length/2; i>=0; i--) {

            heapify(heapSort, i, heapSort.length);
        }

        for(int i= heapSort.length-1; i>=0; i--) {
            int temp = 0;
            temp = heapSort[0];
            heapSort[0] = heapSort[i];
            heapSort[i] = temp;
            heapify(heapSort, 0, i);
        }
    }

    public static void heapify(int[] unsorted, int index, int heapSize) {

        int largest = index;
        int leftIndex = 2*index+1;
        int rightIndex = 2*index+2;
        int temp = 0;

        if(leftIndex < heapSize && unsorted[leftIndex] > unsorted[largest]) {
            largest = leftIndex;
        }
        if(rightIndex < heapSize && unsorted[rightIndex] > unsorted[largest]) {
            largest = rightIndex;
        }

        if(largest != index) {
            temp = heapSort[largest];
            heapSort[largest] = heapSort[index];
            heapSort[index] = temp;

            heapify(heapSort, largest, heapSize);
        }

    }

}