[알고리즘] 힙정렬

힙 정렬이란?

힙 정렬(Heap Sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서,

내림차순 정렬을 위해서는 최대 힙을 구성하고

오름차순 정렬을 위해서는 최소 힙을 구성한다.

힙 정렬은 1964년 J.W.J 윌리엄스에 의해 발명되었고, 같은 해 R.W. 플로이드가 제자리 정렬을 할 수 있는 개선판을 출판하였고 이 방법이 바로 트리정렬 알고리즘을 이용한 방식이다.

내림차순 정렬을 위한 최대 힙(max heap)의 구현

• 힙(heap)은 1차원 배열로 쉽게 구현될 수 있다.
• 정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입한다.
• 최대 힙으로 구성된 배열에서 최댓값부터 삭제한다.

1. 최대 힙(max heap)의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
   아래의 최대 힙(max heap)에 새로운 요소 8을 삽입해보자

2. 최대 힙(max heap)의 삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
   • 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

아래의 최대 힙(max heap)에서 최댓값을 삭제해보자.

힙 소트가 유용할 때

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

  • 최소 힙 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;
}

힙 정렬 특징 정리

• 정렬을 위한 추가적인 메모리가 필요하지 않다. (제자리 정렬 가능)

• 최선, 평균, 최악의 경우의 모두 heapify 과정이 필요하기 때문에 nlogn 을 보장한다.

• 데이터의 순서를 보장하지 못하는 불안정(unstable)정렬이다.

• 힙정렬과 퀵정렬을 비교해보면 똑같은 nlogn 이지만 컴퓨터의 하드웨어 구조상 퀵정렬이 실제로는 더 빠르다고 한다. 이유는 퀵 정렬의 경우는 대개 원소들끼리 근접한 메모리 영역에 붙어 있는 배열을 사용하기 때문에 일반적으로 캐시 친화적이지만 힙정렬의 원소들은 좀 더 흩어져 있는 경우가 많아서 캐시 친화도가 떨어지는 문제가 있고,

  힙정렬은 일반적으로 포인터 연산을 많이 사용하기 때문에 거기에 걸리는 오버헤드도 무시할 수는 없는 수준이기 때문이다

출처

https://hongcoding.tistory.com/186
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/HeapSort.md