[자료구조] 힙 정렬(Heap Sort)

먼저, 힙이란

- 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

 

이 힙을 사용하여 정렬하는 알고리즘이 힙 정렬이다.

- 힙의 루트노드에 저장된 값이 가장 커야한다.

- 힙의 루트 노드에 저장된 값이 정렬 순서상 가장 앞선다.

- 마지막 노드의 값을 부모와 비교하여 자식 노드의 값이 우선순위가 더 높다면 부모노드와 자리를 바꾸는 방식으로 정렬을 진행한다.

- 삽입 : 새로운 노드를 힙의 마지막 노드에 삽입한 후 부모 노드들과 비교하여 정렬한다.

- 삭제 : 힙의 최대값인 루트노드가 삭제되고 마지막 노드가 루트노드로 옮겨진다.

이후 루트노드를 자식노드와 비교하며 정렬한다.

- 시간 복잡도 : O(nlog2n)

 

 

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