힙 정렬

---

출처 위키 - Heap (data structure)

사용 언어 자바

힙 구조

힙 정렬에 대해 알아보려는데 문득 그러고보니 힙이 뭘까?

위키에 의하면 트리 기반의 자료구조로
모든 부모들이 자식들보다 더 높은 기준의 값을 가진다는 특징이 있다

힙 구조는 최고 기준의 노드가 항상 최상위에 있다는 점과
적은 시간복잡도($log_2n$)로 구성이 가능하다는 장점이 있다

이런 힙 구조를 이용해 빠르게 힙 구조를 만들고
최상단에 있는 최고 기준의 노드를 맨 끝 노드와 교환하고
끝 노드를 범위에서 제외하는 것을 반복해 기준 역순의 정렬을 완성하는
힙 정렬($nlog_2n$)을 한번 구현해 보자

순서

• 값 교환
• 부분 힙
• 완전 힙
• 정렬

배열 순서 교환 Swap

배열과 두 인덱스를 전달받아 값을 서로 바꿔준다

private int[] swap(int[] array, int idxA, int idxB) {
    //if (!validRange(array, 0, length - 1)) return null;
    int temp = array[idxA];
    array[idxA] = array[idxB];
    array[idxB] = temp;
    return array;
}

부분 힙 만들기 (최대 힙 기준)

배열과 노드의 인덱스, 배열의 범위를 전달받아
노드의 자식노드가 더 크면 교환해준다

우측 자식노드가 없을 수도 있으므로 유의하자

최고 기준의 노드를 최상단으로 옮기는데에는 문제가 없지만

정렬 목적 외에도 힙 구조를 만드는 것이 중요하다면,
교환 후에는 하위 노드들의 힙 구조에 변화가 생길 수 있으므로
하위 노드들의 힙 구조도 신경써야한다

private int[] maxHeap(int[] array, int parent, int length) {
    int left = parent * 2 + 1;
    int right = parent * 2 + 2;
    int child = left;

    if (length <= left) return null;

    if ((length > right) && (array[left] < array[right])) child = right;

    if (array[parent] < array[child]) {
        swap(array, parent, child);
        maxHeap(array, child, length);  // 선택
    }
    return array;
}

완전 힙 만들기

부분 힙 함수로 부모들만 힙 구조를 만들어줘도 전체를 검사할 수 있다

// 0, 1, .. 9 길이 10
      [0]
   [1]   [2]
 [3][4]  5  6
7 8  9
// (10 / 2) - 1 = [4]
// 4 ~ 0만 하면 된다

배열을 완전이진트리로 봤을때,
(길이 / 2) - 1이 자식을 가진 마지막 부모의 인덱스가 된다
부모들을 모두 순회하면서 완전한 힙 구조를 만들어준다

private int[] heapify(int[] array, int length) {
    //if (!validRange(array, 0, length - 1)) return null;
    for (int parent = length / 2 - 1; parent >= 0; parent--) {
        maxHeap(array, parent, length);
    }
    return array;
}

힙 정렬

완전한 힙은 최상단에 최고 기준의 노드가 있으므로,

최상단의 노드를 끝 노드와 바꾸고 배열 범위에서 제외하면
끝에서부터 최고 기준의 노드 순으로 자리하게 된다

// [9], 5, 7, 2, (1)  ->  (1), 5, 7, 2, [9]  -> // [9]
//    [7], 5, 1, (2)  ->  (2), 5, 1, [7]  ->    // [7], 9
//       [5], 2, (1)  ->  (2), 1, [5]  ->       // [5], 7, 9
//          [2], (1)  ->  (1), [2]  ->      (1) // [2], 5, 7, 9

이것을 반복하면 기준의 역순,  
즉 최대힙의 경우 배열이 오름차 순으로 정렬이 된다  

```java
public int[] heapSort(int[] array) {
    for (int length = array.length; length > 0; length--) {
        heapify(array, length);
        swap(array, 0, length - 1);
    }
    return array;
}