힙 정렬

Heap Sort

이진 합 자료구조를 기반으로 한 정렬 알고리즘입니다. 이 알고리즘은 힙을 사용하여 정렬을 수행하는데, 힙은 부모 노드와 자식 노드 간의 관계를 이용하여 데이터를 정렬합니다.

특징

비교적 불안정한 정렬 방법 중 하나입니다. 동일한 값에 대해 상대적 순서가 바뀔 수 있다.

비교 기반의 정렬 알고리즘으로, 데이터 간의 비교를 기반으로 정렬을 수행합니다.

평균 및 최악의 시간 복접도는 O(n log n)입니다. 이는 효율적인 정렬 알고리즘 중 하나입니다.

분할 정복 방법을 사용하며 배열을 힙으로 구성하고 최대 힙에서 최댓값을 반복적으로 추출하여 정렬을 완성합니다.

과정

최대 힙 구성

먼저 주어진 배열을 최대 힙으로 만듭니다. 최대 힙이란 부모 노드가 항상 자식 노드보다 크거나 같은 트리 구조입니다.

최대 힙 구성 과정

주어진 배열을 힙 구조로 만들기 위해 최대 힙 조건을 만족하도록 배열을 조정합니다.

배열의 요소들을 가지고 트리 구조를 만들어 나갑니다. 이때, 부모 노드는 자식 노드보다 크거나 같은 값을 가져야 합니다.

 

최대 힙에서 최대 값 추출

배열의 첫 번째 요소는 최댓값이 되며, 이를 배열의 맨 끝 요소와 교환합니다.

 

힙 크기 축소 및 재구성

힙에서 최댓값을 주출하며, 배열의 크기를 줄이고 남은 요소를 다시 최대 힙으로 만들어 줍니다.

구현코드

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; // 오른쪽 자식 노드

        // 왼쪽 자식이 루트보다 크면 largest 변경
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // 오른쪽 자식이 루트보다 크면 largest 변경
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // largest가 루트가 아니라면 교환 및 재귀 호출
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 재귀적으로 최대 힙을 만들기 위해 heapify 호출
            heapify(arr, n, largest);
        }
    }
}