[Algorithm] 힙 정렬(Heap Sort)

설명

• 힙 트리 구조를 활용하는 정렬 방식
• 추가 메모리를 사용하지 않으므로 병합 정렬보다 효율적임
• 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.
• 이진트리
  • 자식을 둘 갖는 노드 집합
• 완전 이진 트리
  • 자식을 왼쪽 오른쪽 순서대로 갖는 노드 집합
• 힙
  • 최소값과 최대값을 빠르게 찾아내기 위해 사용하는 완전 이진 트리
• 최대힙
  • 부모가 큰 값, 자식이 작은 값을 갖는 힙
  • 최대힙으로 만들기 위해 힙정렬을 수행(Heapify Algorithm)
• 시간 복잡도 : O(N * logN)
• 참고
  • https://youtu.be/iyl9bfp_8ag

heapify 예시

• 힙정렬 전 이진 트리

  

• 3을 기준으로 정렬
  • 부모가 더 크므로 pass
• 4를 기준으로 정렬
  • 부모가 더 크므로 pass
• 1을 기준으로 정렬
  • 부모가 더 크므로 pass
• 6을 기준으로 정렬
  • 부모(3)가 더 작으므로 위치 변경 → 루트부터 5 6 3
  • 다시 6을 기준으로 부모(5)가 더 작으므로 위치 변경 → 루트부터 6 5 3
• 10을 기준으로 정렬
  • 부모(4)가 더 작으므로 위치 변경 → 루트부터 6 10 4
  • 다시 10을 기준으로 부모(6)가 더 작으므로 위치 변경 → 루트부터 10 6 4
• 최대힙 완성
  • 10 5 6 1 3 4

힙 정렬 예시

• 전체 데이터를 힙정렬(heapify) 수행
• 제일 큰 값(루트)를 가장 마지막 위치로 이동
• 가장 끝 데이터를 제외한 나머지 데이터를 가지고 힙정렬(heapify) 수행
• 정렬 완성까지 위 과정 반복

코드 - v1

public class Solution {
    public static int[] sort(int[] data) {
        // 전체 데이터 힙정렬 (루트가 가장 큰 값이 되도록)
        heapify(data, data.length - 1);

        for (int i = data.length - 1; i >= 0; i--) {
            // 제일 큰 값(루트)을 가장 끝으로 이동
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;

            // 가장 끝 노드를 제외하고 힙정렬
            heapify(data, i - 1);
        }

        return data;
    }

    private static void heapify(int[] data, int max) {
        for (int i = 1; i <= max; i++) {
            int child = i;

            while (child > 0) {
                int parent = (child - 1) / 2;

                // 자식이 부모 보다 크면 위치 변경
                // 내림 차순일 경우 (data[root] > data[child])
                if (data[parent] < data[child]) {
                    int temp = data[parent];
                    data[parent] = data[child];
                    data[child] = temp;
                }

                child = parent;
            }
        }
    }
}

코드 - v2

public class Solution {
    public static int[] sort(int[] data) {
        int size = data.length;

        // 제일 큰 숫자를 root로 끌어 올리는 과정
        for (int i = size / 2 - 1; i >= 0; i--) { // "size / 2 - 1"로 시작하는 이유는 가장 마지막 노드의 부모 노드부터 heapify를 시작하면 되기 때문.
            heapify(data, size, i);
        }

        for (int i = size - 1; i > 0; i--) {
            swap(data, 0, i); // 마지막 노드와 루트 노드의 값을 교환
            heapify(data, i, 0); // 사이즈가 i인 힙의 루트 노드부터 heapify 시작
        }

        return data;
    }

    // root의 자식 중 가장 큰 값을 root와 교환하는 로직
    private static void heapify(int[] data, int size, int root) {
        int target = root; // 왼쪽자식, 오른쪽자식 중 가장 큰 값을 갖는 자식 노드의 인덱스
        int left = root * 2 + 1; // 왼쪽자식 인덱스
        int right = left + 1; // 오른쪽자식 인덱스

        if (left < size && data[target] < data[left]) { // 왼쪽자식이 클 경우 왼쪽자식의 인덱스 저장
            target = left;
        }

        if (right < size && data[target] < data[right]) { // 오른쪽자식이 클 경우 오른쪽자식의 인덱스
            target = right;
        }

        if (root != target) { // 부모보다 큰 값을 갖는 자식이 존재할 경우
            swap(data, target, root); // 부모와 큰 값을 갖는 자식의 값을 교환
            heapify(data, size, target); // 부모보다 큰 값을 가졌던 자식 노드를 기준으로 heapify
        }
    }

    private static void swap(int[] data, int a, int b) {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data -> #result"() {
        expect:
        Solution.sort(data as int[]) == result

        where:
        data                            | result
        [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        [7, 6, 5, 8, 3, 5, 9, 1]        | [1, 3, 5, 5, 6, 7, 8, 9]
    }
}

참고

• https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html
• https://gyoogle.dev/blog/algorithm/Heap%20Sort.html