[java] 힙 정렬 알고리즘

14 Dec 2023

java

힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 사용하여 정렬을 수행하는 알고리즘입니다. 이는 선택 정렬(Selection Sort)의 향상된 버전으로 볼 수 있습니다. 이번 포스팅에서는 자바를 사용하여 힙 정렬을 구현하는 방법을 살펴보겠습니다.

힙 정렬 알고리즘 개요

먼저 주어진 배열을 최대 힙(max heap)으로 만듭니다. 이때, 최대 힙은 부모 노드가 자식 노드보다 항상 큰 값을 가지는 이진트리입니다.
최대 힙에서는 가장 큰 값을 가지는 요소가 항상 루트 노드에 위치하게 됩니다.
루트 노드와 마지막 노드를 교환하고, 마지막 노드를 힙에서 제외시킨 후, 다시 최대 힙을 구성합니다.
위의 과정을 반복하여 정렬을 완성합니다.

자바로 힙 정렬 구현하기

다음은 자바 코드로 구현한 힙 정렬 알고리즘의 예시입니다.

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 l = 2 * i + 1; // 왼쪽 자식 노드
        int r = 2 * i + 2; // 오른쪽 자식 노드

        // 왼쪽 자식이 루트보다 크면 largest를 갱신
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // 오른쪽 자식이 루트보다 크면 largest를 갱신
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // largest가 루트가 아니라면 교환이 필요
        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 : arr) {
            System.out.print(i + " ");
        }
    }
}

이 코드를 실행하면, 입력된 배열이 힙 정렬 알고리즘에 의해 정렬된 결과를 출력할 것입니다.

힙 정렬은 시간 복잡도가 O(nlogn)으로, 안정적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 특히 정확한 결과가 필요할 때 유용하게 사용됩니다.

이상으로 자바로 힙 정렬을 구현하는 방법에 대해 알아보았습니다.