[java] 힙 정렬 알고리즘

04 Dec 2023

java

힙 정렬 알고리즘은 주어진 배열을 최소 힙이나 최대 힙으로 구성한 후, 힙의 루트 값을 반복적으로 제거하여 정렬된 배열을 생성하는 정렬 알고리즘입니다.

알고리즘 원리

주어진 배열을 최대 힙으로 구성합니다.
가장 큰 값을 배열의 마지막 요소와 교환합니다.
힙의 크기를 1 감소시키고, 변경된 힙 구조를 유지하기 위해 힙을 재구성합니다.
위 과정을 반복하여 정렬이 완료될 때까지 실행합니다.

구현 예시

아래는 Java 언어로 힙 정렬을 구현한 예시입니다.

public class HeapSort {
    
    public void sort(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;
 
            // 변경된 힙 구조의 유지
            heapify(arr, i, 0);
        }
    }
 
    void heapify(int arr[], int n, int i) {
        int largest = i; // 루트 노드
        int left = 2 * i + 1; // 왼쪽 자식 노드
        int right = 2 * i + 2; // 오른쪽 자식 노드
 
        // 왼쪽 자식과 비교
        if (left < n && arr[left] > arr[largest])
            largest = left;
 
        // 오른쪽 자식과 비교
        if (right < n && arr[right] > arr[largest])
            largest = right;
 
        // 루트와 가장 큰 값 교환
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            // 변경된 하위 트리에 대해 힙 구조 유지
            heapify(arr, n, largest);
        }
    }
 
    public static void main(String args[]) {
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        int n = arr.length;
 
        HeapSort heapSort = new HeapSort();
        heapSort.sort(arr);
 
        System.out.println("힙 정렬된 배열:");
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
    }
}

위의 예시에서는 주어진 배열 { 12, 11, 13, 5, 6, 7 }를 힙 정렬로 정렬한 후, 결과를 출력합니다.

이와 같이 힙 정렬 알고리즘을 구현할 수 있으며, 해당 알고리즘은 시간 복잡도 O(nlogn)을 가지고 있습니다.

알고리즘 원리

구현 예시

참고 자료