힙 정렬 (Heap Sort) - Java (ing)

힙 정렬(Heap Sort)이란?

• 시간 복잡도 : O(NlogN)
• 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)만큼 빠른 정렬 알고리즘
• 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법
  => 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 한다. 
• 힙 정렬의 아이디어 => "힙(Heap)을 이용해 데이터를 정렬하면 어떨까?"

 

Heap 이란?

• 이진 트리 : 모든 노드의 자식 노드가 2개 이하인 트리
• 완전 이진 트리 : 이진트리의 노드가 중간에 비어있지 않고 빽빽히 왼쪽부터 가득 찬 구조
• 힙(Heap)
  • 최소값이나 최대값을 빠르게 찾아내기 위해 완전 이진트리를 기반으로 하는 트리
  • 힙에는 최대 힙과 최소 힙이 존재한다. 
  • 최대 힙 : '부모 노드' 가 '자식 노드' 보다 큰 구조

 

 

 

최대 힙 구조에서의 힙 정렬

• 모든 부모 노드가 자식 노드보다 큰 값을 가져야 한다. 

• 최초로 자식노드를 갖는 레벨 부터 시작
  • 루트 노드를 0번 인덱스라고 가정했을 때, 
  • 전체 노드의 수를 2로 나눈 수에 해당하는 인덱스부터 시작하면 된다. 
  • (위의 그림이라면 전체 노드의 수가 5개이므로 2로 나눈 2번 인덱스에 해당하는 노드(value = 3) 부터 시작 
• 자식 노드 중 더 큰 값을 부모 노드와 비교
  • 자식노드의 값이 더 클 경우 부모노드와 자리를 바꾼다. 
    => 2번 인덱스의 노드는 자식이 없으므로 자동으로 힙구조 성립.
    => 1번 인덱스(2) 노드의 자식 노드 4, 5 중 큰 값인 5를 자신의 값과 비교, 자식 노드 값이 더 크므로 자리를 바꾼다. 

• 자리가 바뀐 노드(2)를 또 그 자식 노드와 비교한다.
  => 현재는 더이상 자식이 없으므로 힙 성립
• 루트 노드까지 비교 작업 반복 

• 최대 힙 구조 완성
• 최대 힙 구조에서 루트 노드는 가장 큰 값을 가지고 있다. 
• 루트 노드와 말단 노드를 바꾼다. 
• 다시 힙구조로 바꾸는 작업 반복

 

힙 정렬 구현 - 최대 힙 구조 (1.  힙 정렬 직접 구현) 

public class MaxHeapSort {
    public static int[] maxHeapSort(int[] arr) {
        sort(arr);
        return arr;
    }
    public static void sort(int[] arr) {
        System.out.println("최초 입력받은 배열");
        System.out.println(Arrays.toString(arr));

        heapify(arr, arr.length);

        for(int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            System.out.println("최대값을 맨 뒤와 바꾼 후 배열");
            System.out.println(Arrays.toString(arr));
            heapify(arr, i);
        }
    }

    // 힙구조 완성하기
    public static void heapify(int[] arr, int idx) {
        for(int i = 1; i < idx; i++) { // i = 1 부터인 이유 : 자식노드를 확인해야 하므로 루트노드 제외
            int child = i;
            while(child > 0) {
                int parent = (child - 1) / 2;
                if(arr[child] > arr[parent]) {
                    swap(arr, child, parent);
                }
                child = parent;
            }
        }
        System.out.println("최대 힙 구조로 변환한 배열");
        System.out.println(Arrays.toString(arr));
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr1 = {28, 132, 98, 30, 1, 4895, 52, 7, 123};
        int[] arr2 = {7,7,3,2,1,8,9,10,10,7};

        System.out.println(Arrays.toString(maxHeapSort(arr1)));
        System.out.println(Arrays.toString(maxHeapSort(arr2)));
    }
}

 

힙 정렬 구현 - 최소 힙 구조 (2. PriorityQueue 이용)

자바에는 PriorityQueuer 가 heap 구조를 자동으로 구현해주어, 정말 간단하게 힙정렬을 구현할 수도 있다. 

public class MinHeapSort {
    public static int[] minHeapSort(int[] arr){
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        for(int i = 0; i < arr.length; i++) {
            heap.add(arr[i]);
        }

        for(int i = 0; i < arr.length; i++) {
            arr[i] = heap.poll();
        }

        return arr;
    }

    public static void main(String[] args) {
        int[] output = minHeapSort(new int[]{5, 4, 3, 2, 1});
        System.out.println(Arrays.toString(output)); // --> [1, 2, 3, 4, 5]

        output = minHeapSort(new int[]{3, 1, 21});
        System.out.println(Arrays.toString(output)); // --> [1, 3, 21]

        output = minHeapSort(new int[]{4, 10, 3, 5, 1});
        System.out.println(Arrays.toString(output)); // --> [1, 3, 4, 5, 10]
    }
}