[알고리즘] 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

• 힙 자료구조를 기반으로 하는 정렬 알고리즘
• 시간복잡도 : O(nlogn)
• 공간복잡도 : O(n)
• 장점 : 효율적이며 추가적인 메모리 공간이 불필요하다.
• 단점
  • 불안정한 정렬이다.
  • 힙 자료구조를 구성하고 유지하기 위해 추가적인 구현이 필요하다.
  • 루트 노드에서 최댓값 또는 최솟값을 추출하고 배열의 마지막 요소와 교환하는 과정을 반복하기 때문에 요소들의 이동 횟수가 많을 수 있다.

힙 정렬 프로세스

1. 배열을 힙으로 만들기 (Max Heap 또는 Min Heap 구성)
   • Bottom-up 방식으로 시작
   • 주어진 배열을 이진 트리로 간주하고, 가장 마지막 레벨의 부모 노드부터 시작하여 루트 노드까지 차례대로 아래로 내려가며 힙의 특성을 만족하도록 조정 (Heapify 과정)
2. 최대 힙 또는 최소 힙에서 최댓값 또는 최솟값 추출
   • 힙으로 만들어진 배열에서 루트 노드에 위치한 최댓값(또는 최솟값)을 추출
   • 추출된 최댓값(또는 최솟값)을 배열의 가장 마지막 요소와 교환
3. 힙의 크기를 줄이고, 다시 Heapify 진행
   • 추출된 요소를 배열의 뒷부분으로 보내고, 힙의 크기를 1만큼 감소
   • 감소된 크기의 힙을 대상으로 Heapify 과정을 반복하여 힙의 특성을 유지
4. 위 과정을 반복하여 정렬
   • 힙의 크기가 1보다 큰 동안 위 과정을 반복
   • 최종적으로 정렬된 요소들은 배열의 앞부분부터 차례대로 채워진다.

힙 정렬 구현

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 배열을 힙으로 변환
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 최대 힙에서 요소 추출 및 정렬
        for (int i = n - 1; i > 0; i--) {
            // 최대 힙에서 최댓값(루트 노드)을 추출하고 배열의 마지막 요소와 교환
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 힙 크기를 1 감소시키고, 다시 힙 구성
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int root) {
        int largest = root; // 부모 노드
        int left = 2 * root + 1; // 왼쪽 자식 노드
        int right = 2 * root + 2; // 오른쪽 자식 노드

        // 왼쪽 자식 노드가 힙 크기 내에 있고 부모보다 큰 경우
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 오른쪽 자식 노드가 힙 크기 내에 있고 부모나 왼쪽 자식보다 큰 경우
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 부모 노드와 가장 큰 자식 노드를 교환
        if (largest != root) {
            int temp = arr[root];
            arr[root] = arr[largest];
            arr[largest] = temp;

            // 교환된 자식 노드를 기준으로 다시 힙 구성
            heapify(arr, n, largest);
        }
    }