[java] 자바 힙의 데이터 정렬하기

08 Dec 2023

java

자바에서 데이터를 효율적으로 정렬하는 방법 중 하나는 힙(Heap)을 사용하는 것입니다. 힙은 트리 기반의 자료구조로, 데이터를 저장하면서 항상 루트 노드가 가장 크거나 작은 값을 가지도록 구성됩니다. 이를 통해 정렬되지 않은 데이터를 효율적으로 정렬할 수 있습니다.

힙 정렬 알고리즘

힙 정렬 알고리즘은 다음과 같은 단계로 이루어집니다:

정렬되지 않은 데이터를 힙으로 구성합니다.
루트 노드를 제거하고 저장합니다.
나머지 데이터를 다시 힙으로 구성합니다 (재구성).
위 과정을 반복하여 모든 데이터를 정렬합니다.

자바에서 힙 정렬 사용하기

아래는 자바 코드를 사용하여 힙 정렬을 구현하는 예시입니다:

import java.util.Arrays;

public class HeapSort {
    public static 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);
        }
    }

    static void heapify(int arr[], int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        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};
        sort(arr);
        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

위 코드에서 heapify 함수는 힙의 재구성을 담당하고, sort 함수를 통해 전체적인 힙 정렬이 이루어집니다.

힙 정렬은 시간 복잡도가 O(n log n)으로 효율적인 정렬 알고리즘 중 하나입니다.

마치며

힙을 사용한 효율적인 데이터 정렬 알고리즘에 대해 알아보았습니다. 힙 정렬은 배열 기반의 정렬 방법 중 하나로, 대량의 데이터를 정렬할 때 유용하게 사용될 수 있습니다.

더 자세한 내용은 다음 참고 자료를 참고할 수 있습니다:

GeeksforGeeks - Heap Sort