[알고리즘] 힙 정렬 ( Heap Sort )

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

 

완전 이진 트리

삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리

 

힙 정렬은 불안정 정렬에 속한다.

 

시간복잡도

평균 : O(nlogn)

최선 : Ω(nlogn)

최악 : O(nlogn)

 

과정

1. 최대 힙을 구성한다.

2. 현재 힙 루트에 가장 큰 값이 존재. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈를 하나 줄인다.

3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다.

 

루트를 마지막 노드로 대체 ( 11 -> 4 ), 다시 최대 힙을 구성

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

 

---

 

public void heapSort(int[] array) {
    int n = array.length;
    
    // max heap 초기화
    for (int i = n/2-1; i>=0; i--){
        heapify(array, n, i); // 1
    }
    
    // extract 연산
    for (int i = n-1; i>0; i--) {
        swap(array, 0, i); 
        heapify(array, i, 0); // 2
    }
}

 

1번째 heapify

 - 일반 배열을 힙으로 구성하는 역할

   자식노드로부터 부모노드 비교

 n / 2-1 부터 0 까지 인덱스가 도는 이유 

   - 부모 노드의 인덱스를 기준으로 왼쪽 자식노드 ( i2 + 1 ), 오른쪽 자식 노드 ( i2 + 2 )이기 때문

 

2번째 heapify

 요소가 하나 제거된 이후에 다시 최대 힙을 구성하기 위함

 루트를 기준으로 진행 ( extract 연산 처리를 하기 위함 )

public 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);
    }
}

 

다시 최대 힙을 구성할 때까지 부모 노드와 자식 노드를 swap하며 재귀로 진행한다.

퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다.

하지만 힙 자료구조가 많이 활용되고 있고, 이때 합께 따라오는 개념이 힙 정렬이다.

 

힙 정렬이 유용할 때

- 가장 크거나 가장 작은 값을 구할 때

• 최소 힙  or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능하다.

- 최대 k 만큼 떨어진 요소들을 정렬할 때

• 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다.

---

 

전체 코드

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;
}