힙 정렬(Heap Sort)

힙 정렬

완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식

완전 이진 트리?
삽입할 떄 왼쪽부터 차례대로 추가하는 이진 트리

힙 소트는 불안정 정렬에 속함

과정

1. 최대 힙을 구성
2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
3. 힙의 사이즈가 1보다 크면 위 과정 반복

루트(최대 값)을 빼내고 마지막 노드로 대체(11 -> 4)후 다시 최대 힙 구성

이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것이 힙 소트

코드

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    heapSort(array);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void heapify(int array[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
 
    if (l < n && array[p] < array[l]) {
        p = l;
    }
 
    if (r < n && array[p] < array[r]) {
        p = r;
    }
 
    if (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
 
public static void heapSort(int[] array) {
    int n = array.length;
 
    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
 
    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

힙 소트가 유용할 때

• 가장 크거나 가장 작은 값을 구할 때
  최소 힙 or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는것이 가능
• 최대 k 만큼 떨어진 요소들을 정렬할 때
  삽입 정렬보다 더욱 개선된 결과를 얻어낼 수 있음

📝참고

https://gyoogle.dev/blog/algorithm/Heap%20Sort.html