힙 정렬

힙 정렬 (Heap Sort)

힙 정렬은 완전 이진 트리를 기반으로 하는 힙(Heap) 자료구조를 이용하여 데이터를 정렬하는 알고리즘입니다. 최대 힙 또는 최소 힙을 구성하여 순차적으로 요소를 꺼내어 정렬을 수행합니다.

핵심 요소

•

힙(Heap) 자료구조 활용

•

완전 이진 트리 기반

•

불안정 정렬

•

제자리 정렬(in-place sorting)

시간 복잡도

최선의 경우	O(nlog n)
평균의 경우	O(nlog n)
최악의 경우	O(nlog n)
공간 복잡도	O(1)

주요 특징

•

항상 O(nlog n)의 시간 복잡도를 보장

•

추가 메모리 공간이 거의 필요하지 않음

•

대규모 데이터 정렬에 효율적

•

불안정 정렬이므로 동일한 값의 순서가 보장되지 않음

예시 코드 (Java)

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;
        
        if (left < n && arr[left] > arr[largest])
            largest = left;
            
        if (right < n && arr[right] > arr[largest])
            largest = right;
            
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            
            heapify(arr, n, largest);
        }
    }
}
Java
복사

직접 구현

public class MyHeapSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        HeapSort hs = new HeapSort();
        hs.sort(arr);
        
        System.out.println("정렬된 배열:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
Java
복사

Java Collections으로 구현

import java.util.PriorityQueue;

public class HeapSortWithPQ {
    public static void heapSort(int[] arr) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        // 배열의 모든 요소를 힙에 추가
        for (int value : arr) {
            heap.offer(value);
        }
        
        // 힙에서 요소를 하나씩 꺼내어 배열에 저장
        for (int i = 0; i < arr.length; i++) {
            arr[i] = heap.poll();
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        heapSort(arr);
        
        System.out.println("정렬된 배열:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
Java
복사