힙 정렬(Heap sort) - 자바(JAVA)

힙 정렬(Heap sort) - 자바(JAVA)

힙 정렬에 대해 알아보자.

힙 자료구조를 이용한 정렬이다.

힙(Heap) 이란?

• 완전 이진 트리 형태
• 부모 노드가 자식 노드보다 큰 값을 가짐

위 두가지 조건을 만족하는 자료구조를 힙(Heap)이라 부른다.

힙은 보통 배열로 많이 구현을 한다.

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
자세한건 위 블로그를 참고하자.

힙 정렬의 순서

1. 배열을 힙으로 만든다
2. 만든 힙으로 정렬을 한다

오름차순으로 정렬 => 최대 힙 이용
내림차순으로 정렬 => 최소 힙 이용

트리(배열)를 힙으로 만드는 과정

1. 자식이 있는 가장 마지막 부모 노드부터 힙으로 만든다.
2. 거슬러 올라가면서 더 큰 힙을 만든다.
3. root 노드까지 힙으로 만들면 배열 전체가 힙이 된다.

트리(배열)을 힙으로 만드는 방법

• 자식 노드가 2개인 경우
  부모 노드와 자식 노드를 비교해서, 가장 큰 값을 가지는 노드의 값을 부모 노드의 값과 교환한다. (부모 노드의 값이 가장 크다면 교환하지 않는다)

• 자식 노드가 한개인 경우
  부모, 자식노드의 값을 비교해서 자식노드의 값이 더 크다면 교환한다. (아니라면 교환하지 않는다.)

힙을 정렬하는 방법

1. root 노드의 값을 바깥으로 빼고, 가장 마지막 leaf노드의 값을 root노드의 값으로 넣는다.
   (배열에서는 root노드의 값을 가장 마지막 leaf 노드의 값과 교환하고 힙의 크기를 1 줄인다 --> 1개를 뺀 것처럼 동작)

2. 힙의 구조가 깨졌으므로, 다시 힙으로 수정한다.

3. 1번과 2번을 반복하다가, 더이상 뺄 값이 없다면 정렬 완료이다. (힙의 크기가 0이 된 경우)

import java.util.*;

class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.println("배열의 크기를 입력하시오");
        int n = scanner.nextInt()+1;
        int[] arr = new int[n];

        System.out.println("배열에 들어갈 숫자를 입력하시오");
        for(int i = 1; i<n; i++) {
            arr[i] = scanner.nextInt();
        }

        System.out.println("배열에 입력한 숫자");
        System.out.println(Arrays.toString(arr));

        buildHeap(arr); //배열을 힙으로 만드는 메서드

        System.out.println("힙으로 변경한 배열");
        System.out.println(Arrays.toString(arr));

        heapSort(arr); //힙을 이용해서 정렬하는 메서드

        System.out.println("정렬 완료된 배열");
        System.out.println(Arrays.toString(arr));
    }

    static void heapSort(int[] arr) {
        int eNN = arr.length-1;
        while(eNN > 1) {
            swap(arr, 1, eNN);
            eNN--;
            pushDown(arr, 1, eNN);
        }
    }

    //eNN = endNodeNumber
    //tNN = tempNodeNumber
    static void buildHeap(int[] arr) {
        int eNN = arr.length - 1; // 마지막 노드
        int tNN = eNN/2 + 1; //1번째 리프노드 번호

        while(tNN > 1) {
            tNN--; // 자식을 가지고 있는 마지막 노드부터 시작
            pushDown(arr, tNN, eNN);
        }
    }

    static void pushDown(int[] arr, int tNN, int eNN) {
        int y = findLarger(arr, tNN, eNN); 
        //자식 노드중에서 루트 노드보다 더 큰 값을 가지는 노드 번호 얻어냄

        while(arr[tNN] < arr[y]){
            swap(arr, tNN, y);
            tNN = y;
            y = findLarger(arr, tNN, eNN);
            // leaf노드 쪽으로 내려가면서 값의 제자리를 찾아간다.
        }
    }

    static int findLarger(int[] arr, int tNN, int eNN){
        int tmp = tNN*2+1; //오른쪽 자식 노드의 번호
        int y = tNN;

        if(tmp <= eNN){//자식 노드가 두개인 경우
            if(arr[tNN] < arr[tmp]) //오른쪽 자식 노드의 value가 더 크다면
                y = tmp;
            if(arr[y] < arr[tmp-1]) //왼쪽 자식 노드의 value가 더 크다면
                y = tmp-1;
        }
        else if(tmp-1 <= eNN){ //자식 노드가 1개인 경우
            if(arr[tNN] < arr[tmp-1]) // 자식 노드의 value가 더 크다면
                y = tmp-1;
        }
        return y;
    }

    static void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

만약, 구현되어있는 메서드를 사용하고 싶다면,
아래의 코드를 참고하자

class Main {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();

        int[] arr = {3,1,5,2,4};
        for(int i=0; i<arr.length; i++)
            pq.offer(arr[i]);

        System.out.println(pq);

        Object obj = null;
        int a = 0;
        while((obj = pq.poll())!=null)
            System.out.printf("%s ",obj);
    }
}

Queue의 구현체 PriorityQueue클래스를 이용해서 정렬한 코드이다.
pq객체에 값을 추가할 때, 힙의 형태로 담기게 된다

고찰

• 힙이 많이 사용해보지 않은 자료구조라서 조건이나 만들어지는 과정이 꽤 헷갈렸다.

• 배열을 사용할 때, 범위지정을 실수해서 예외가 발생했다.

참고서적

• 자바의 정석 3판 (남궁성)
• 자바로 쉽게 배우는 알고리즘 (이충기)