힙정렬

출처: https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif

 

힙(Heap)

힙은 이진 트리로서 두 가지 조건을 만족해야 한다

• 완전 이진 트리(Complete Binary Tree)
  • 모든 레벨이 꽉 차야 하며
  • 마지막 레벨은 왼쪽부터 채운다
• 힙 속성(Heap Property)
  • 최대 힙(Max Heap)
    • 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
  • 최소 힙(Min Heap)
    • 부모 노드의 값이 자식 노드의 값보다 작거나 같다.

 

 

힙 정렬 절차

1. 힙 만들기

• 주어진 배열을 힙 자료구조로 변환한다.
• 일반적으로 최대 힙(Max Heap)을 사용하여 배열의 루트 노드가 가장 큰 값이 되게 한다.

2. 정렬 과정

①  루트 노드를 마지막 노드와 교환한다.

②  배열의 크기를 1 줄이고, 루트부터 다시 힙 속성을 만족하도록 조정한다.

③  이 과정을 배열 크기가 1이 될 때까지 반복한다.

 

 

특징

• 시간 복잡도
  • 최악, 평균, 최선
    • O(n log n)
    • 힙을 만드는 데 O(n) 시간이 걸리고 힙을 정렬하는 과정에서 O(log n) 시간이 소요
    • 전체적으로는 O(n log n)
• 공간 복잡도
  • O(1)
  • 힙 정렬은 제자리 정렬(In-place Sort)이므로 추가적인 메모리 공간을 거의 사용하지 않는다.
• 안정성
  • 힙 정렬은 비안정 정렬(Unstable Sort)
  • 동일한 값이 여러 번 등장할 경우 원래의 순서가 유지되지 않는다.

 

 

장점

• 시간 복잡도가 일정
  • 최악의 경우에도 O(n log n) 
• 제자리 정렬
  • 추가 메모리가 거의 필요 없어서 공간 효율적
• 우선순위 큐
  • 힙 자료구조는 우선순위 큐 구현에 유용

 

단점

• 비안정 정렬
  • 동일한 값이 여러 번 등장할 경우 순서가 보장되지 않는다.
• 상대적으로 복잡
  • 다른 정렬 알고리즘보다 구현이 다소 복잡
  • 실제 성능은 퀵 정렬에 비해 떨어질 수 있다.

 

JAVA

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1  # 왼쪽 자식
    right = 2 * i + 2  # 오른쪽 자식

    # 왼쪽 자식이 더 큰 경우
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 오른쪽 자식이 더 큰 경우
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 가장 큰 값이 루트가 아닌 경우
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 교환
        heapify(arr, n, largest)  # 재귀적으로 힙 속성 복구

def heap_sort(arr):
    n = len(arr)

    # 힙 만들기
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 힙에서 요소 하나씩 빼서 정렬
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 교환
        heapify(arr, i, 0)  # 힙 속성 복구


arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("정렬 후:", arr)

 

Python

public class HeapSort {
    public static 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 temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);  // 재귀적으로 힙 속성 복구
        }
    }

    public static void heapSort(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[i];
            arr[i] = arr[0];
            arr[0] = temp;
            heapify(arr, i, 0);  // 힙 속성 복구
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        heapSort(arr);
        System.out.println("정렬 후: " + java.util.Arrays.toString(arr));
    }
}