[java] 자바 힙을 이용한 데이터 정렬 예시

08 Dec 2023

java

힙(Heap)은 완전 이진 트리 자료구조의 일종으로, 각 노드의 값이 그 자식 노드의 값보다 항상 크거나 작도록 구성된 이진 트리입니다. 힙을 사용하여 데이터를 정렬할 때는 최대 힙 또는 최소 힙을 활용합니다.

아래는 Java에서 힙을 이용하여 데이터를 정렬하는 예시 코드입니다.

import java.util.Arrays;

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;

        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};
        HeapSort heapSort = new HeapSort();
        heapSort.sort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

위 코드는 HeapSort 클래스를 사용하여 데이터를 힙 정렬하는 방법을 보여줍니다.

힙 정렬은 전통적인 선택 정렬의 시간 복잡성인 O(n²)보다 빠른 O(n log n)의 시간 복잡성을 가지고 있어 대규모 데이터에 대한 정렬에 유용하게 사용됩니다. 힙 정렬은 또한 내부 정렬 알고리즘 중 하나로, 입력 데이터 크기에 관계없이 동일한 시간 복잡성을 보장합니다.

만약 힙 정렬의 더 자세한 내용이 필요하다면 다음 자료를 참고해보십시오: