힙정렬

힙정렬(Heap Sort)은 선택 정렬의 한 종류로, 최대 힙(또는 최소 힙) 자료구조를 이용하여 정렬하는 알고리즘이다.

힙정렬은 항상 n logn 이다.

Heap이란?

트리 기반의 데이터 구조로 완전 이진 트리이다.
최대 힙 (Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같다. 루트 노드는 항상 최대 값을 가진다.
최소 힙 (Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같다. 루트 노드는 항상 최소 값을 가진다.
최소힙 예     1
                  /  \
                3    5
               /  \   /  \
             4  8  6  9

기본적인 동작 방식

1. 주어진 배열을 최대 힙(또는 최소 힙) 구조로 만든다. 이는 부모 노드가 자식 노드들보다 크거나(최대 힙) 작은(최소 힙) 구조를 갖도록 조정하는 과정이고 이를 힙화(Heapify)라고 한다.
2. 최상단 노드(루트 노드)를 배열의 가장 마지막 요소와 교환한다. 이로써 가장 큰(또는 가장 작은) 요소가 배열의 마지막에 위치하게 된다.
3. 힙 크기를 하나 줄이고(마지막 요소를 힙에서 제외시킴) 다시 최대 힙(또는 최소 힙) 속성을 만족하도록 힙을 조정한다.
4. 위 과정을 반복하여 전체 배열이 정렬될 때까지 진행한다.

public class HeapSort {
    
    // 힙 정렬 알고리즘
    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--) {
            // 현재 루트를 끝으로 이동
            swap(arr, 0, i);
 
            // 축소된 힙에서 힙 정렬 재귀 호출
            heapify(arr, i, 0);
        }
    }
 
    // 배열의 인덱스 i를 루트로 하는 서브트리를 힙으로 만드는 함수
    static void heapify(int[] arr, int n, int i) {
        int largest = i; // 현재 루트를 가장 큰 값으로 초기화
        int left = 2 * i + 1; // 왼쪽 자식 노드 인덱스: 2*i + 1
        int right = 2 * i + 2; // 오른쪽 자식 노드 인덱스: 2*i + 2
 
        // 왼쪽 자식이 현재 루트보다 크면 largest를 왼쪽 자식으로 변경
        if (left < n && arr[left] > arr[largest])
            largest = left;
 
        // 오른쪽 자식이 현재 largest보다 크면 largest를 오른쪽 자식으로 변경
        if (right < n && arr[right] > arr[largest])
            largest = right;
 
        // largest가 현재 루트가 아니라면 교환 후 재귀적으로 힙 구성
        if (largest != i) {
            swap(arr, i, largest);
 
            // 영향을 받은 서브트리에 대해 재귀적으로 heapify 호출
            heapify(arr, n, largest);
        }
    }

    // 배열의 두 요소를 교환하는 swap 메서드
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}