[정렬] 힙 정렬 : Heap Sort

 

 

📌 힙 정렬 : Heap 정렬

✅ 이진 힙을 사용하려 데이터를 정렬하는 알고리즘

✅ 최대 힙(Max-Heap) 또는 최소 힙(Min-Heap)을 사용하여 배열을 정렬

✅ 시간복잡도 : \(O(n \log n)\)

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        heapSort(arr);
        System.out.println("결과: " + Arrays.toString(arr));
    }

    private static int getParent(int child) {
        return (child - 1) / 2;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void heapSort(int[] arr) {
        int size = arr.length;

        if(size < 2){
            return;
        }
        
        //배열을 최대힙으로 변환
        int parentIdx = getParent(size - 1); //마지막 노드의 부모 인덱스 계산
        for(int i = parentIdx; i >= 0; i--){ //모든 부모 노드에 대해 heapify 호출
            heapify(arr, i, size - 1);
        }
        
        //힙에서 루트와 마지막 노드 교환 후, 힙 크기 줄이고 재정렬
        for(int i = size - 1; i > 0; i--){
            swap(arr, 0, i); //최대값(루트)와 마지막 노드 교환
            heapify(arr, 0, i - 1); //힙 크기 줄이고 재정렬
        }

    }

    private static void heapify(int[] arr, int parentIdx, int lastIdx){
        int leftChildIdx = 2 * parentIdx + 1;
        int rightChildIdx = 2 * parentIdx + 2;
        int largestIdx = parentIdx;

        if(leftChildIdx <= lastIdx && arr[largestIdx] < arr[leftChildIdx]){
            largestIdx = leftChildIdx;
        }

        if(rightChildIdx <= lastIdx && arr[largestIdx] < arr[rightChildIdx]){
            largestIdx = rightChildIdx;
        }

        if(parentIdx != largestIdx){
            swap(arr, largestIdx, parentIdx); //부모와 가장 큰 자식 노드 교환
            heapify(arr, largestIdx, lastIdx); //변경된 자식 노드에 대해 재귀 호출
        }
    }
}

 

1. 힙 생성 : 주어진 배열을 힙 자료구조로 변환

2. 정렬 : 힙의 루트 노드를 배열의 끝으로 이동, 힙 크기를 줄인 뒤 힙 속성을 유지하도록 재정렬

 

Reference.

 

자바 [JAVA] - 힙 정렬 (Heap Sort)