힙 정렬(Heap Sort) 구현하기(Java)

힙 정렬(Heap Sort)

• 힙의 성질을 이용해 정렬하는 정렬 방식입니다.
  • Cf. 힙의 성질: 힙은 항상 느슨한 정렬 상태를 유지하고, 루트 노드의 key값이 트리 내에서 가장 높거나 낮다(최대/최소힙)
• 일반적으로 \(O(n\log{n})\)의 시간 복잡도를 가집니다. (노드 하나를 재정렬 하는데에 \(O(\log{n})\)의 시간 복잡도 소요)

구현 코드

처음에는 Heap을 구현해서 Array를 인자로 받아 Heap을 채워 heapify 한 뒤, 하나씩 delete해서 루트를 얻어내 값을 정렬할 생각이었습니다. 그런데 그러자니 Heap 내부의 Array를 생성하는 과정이 들기 때문에 추가로 메모리가 들게 되어 추가 메모리가 사용되지 않게 해보자는 취지로 아래와 같이 작성했습니다.

• 먼저, Array를 받아다가 heapify(아래 코드에서는 `shiftDown` 메서드)합니다.
  
  • 보통 Heap Sort가 아닌 Heap만을 구현할 때는 `add()` 혹은 `delete()` 할 때마다 heapify되기 때문에 삽입/삭제 시 한번씩만 수행됩니다.
  • 하지만, 힙이 아닌 이진 트리(배열)을 heapify하기 위해서는 가장 마지막 부모 노드(자식 노드가 존재하는 노드)에서부터 루트 노드까지 반복해서 shift-down하는 과정을 거쳐야 합니다.
• Heap이 된 Array의 루트 노드를 맨 뒤로 보냅니다. (이 때, 전제는 Max Heap이어야 합니다. 루트 노드가 전체 트리 내에서 가장 높은 값이기 때문에 Array의 마지막(보통은 작은 편에 속하는 값)과 바꾸어 줍니다.
• 그 이후에는 0(기존에 Max Heap이 된 Array의 가장 마지막에 있던 작은 값이 옮겨온 인덱스)를 인자로 넘겨주어 해당 인덱스부터 heapify 합니다.
  • 이 때, 마지막 인덱스 값은 기존의 마지막 인덱스 값 - 1이 되어야 합니다. (루프가 반복될 때마다 1씩 계속해서 줄어야합니다.) 왜냐하면, 가장 높은 값을 마지막 인덱스에 옮김으로써 배열의 맨 뒤에서부터 정렬이 수행되고 있기 때문에 이미 정렬된 값은 움직이지 않게 하고 나머지 값들을 정렬하기 위해서입니다. (정확히는 나머지 값들 중에서 가장 높은 루트를 구해야 다음 루프 때 정렬할 수 있기 때문입니다.)

import java.util.Arrays;
import java.util.Random;

public class HeapSort {
    public static void main(String[] args) {
        Random random = new Random();

        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(49) + 1;
        }
        System.out.println("arr: " + Arrays.toString(arr));

        MaxHeap.heapSort(arr);
        System.out.println("arr(after heap sort): " + Arrays.toString(arr));
    }

    static class MaxHeap {
        private static void swap(int[] list, int idx0, int idx1) {
            int val = list[idx0];
            list[idx0] = list[idx1];
            list[idx1] = val;
        }

        /**
         * 힙 또는 힙이 아닌 배열을 재정렬
         *
         * @param list 배열
         * @param idx 재정렬을 시작할 부모 노드 인덱스
         * @param lastIdx 마지막 인덱스보다 작아야 노드가 존재하는 것이기 때문에 이를 위해 넣음
         *                (sorting시 추가적인 메모리 사용을 막기 위해 기존 배열을 heapify(shift-down)한 뒤
         *                루트 노드를 맨 뒤 요소와 바꾸면서 재정렬하는 길이를 1씩 줄임(루트 요소와 맞바꾼 요소는
         *                더이상 sorting되지 않도록 하기 위함)
         */
        private static void shiftDown(int[] list, int idx, int lastIdx) {
            int cIdx0 = idx * 2 + 1;
            int cIdx1 = idx * 2 + 2;

            int targetIdx = idx;
            if (cIdx0 <= lastIdx && list[cIdx0] > list[targetIdx]) {
                targetIdx = cIdx0;
            }

            if (cIdx1 <= lastIdx && list[cIdx1] > list[targetIdx]) {
                targetIdx = cIdx1;
            }

            if (targetIdx != idx) {
                swap(list, targetIdx, idx);
                shiftDown(list, targetIdx, lastIdx);
            }
        }

        /**
         * 정렬되지 않은 배열(이진 트리)를 힙 속성을 만족하도록 재정렬(heap sort)
         * @param list 외부 배열
         * @return result
         */
        public static void heapSort(int[] list) {
            if (list.length < 2) {
                return;
            }

            int parentIdx = (list.length - 1) / 2;
            int lastIdx = list.length - 1;

            for (int i = parentIdx; i >= 0; i--) { // 재정렬
                shiftDown(list, i, lastIdx);
            }

            System.out.println("1차로 전체 heapify : " + Arrays.toString(list));

            for (int i = list.length - 1; i >= 0; i--) {
                swap(list, 0, i); // 마지막 요소부터 하나씩 앞으로 당기며 root값 가짐
                System.out.println(i + "번째 값: " + list[i] + ", 현재 list: " + Arrays.toString(list));
                lastIdx--;
                shiftDown(list, 0, lastIdx);
            }
        }
    }
}

(실제로 정렬되고 있는 과정을 출력하기 위해 임시로 System.out.println을 넣었습니다.)

결과

arr: [11, 49, 46, 2, 1, 44, 18, 2, 14, 33]
1차로 전체 heapify : [49, 33, 46, 14, 11, 44, 18, 2, 2, 1]
9번째 값: 49, 현재 list: [1, 33, 46, 14, 11, 44, 18, 2, 2, 49]
8번째 값: 46, 현재 list: [2, 33, 44, 14, 11, 1, 18, 2, 46, 49]
7번째 값: 44, 현재 list: [2, 33, 18, 14, 11, 1, 2, 44, 46, 49]
6번째 값: 33, 현재 list: [2, 14, 18, 2, 11, 1, 33, 44, 46, 49]
5번째 값: 18, 현재 list: [1, 14, 2, 2, 11, 18, 33, 44, 46, 49]
4번째 값: 14, 현재 list: [1, 11, 2, 2, 14, 18, 33, 44, 46, 49]
3번째 값: 11, 현재 list: [1, 2, 2, 11, 14, 18, 33, 44, 46, 49]
2번째 값: 2, 현재 list: [2, 1, 2, 11, 14, 18, 33, 44, 46, 49]
1번째 값: 2, 현재 list: [1, 2, 2, 11, 14, 18, 33, 44, 46, 49]
0번째 값: 1, 현재 list: [1, 2, 2, 11, 14, 18, 33, 44, 46, 49]
arr(after heap sort): [1, 2, 2, 11, 14, 18, 33, 44, 46, 49]

 

참고

https://st-lab.tistory.com/205