Heap Sort 및 Heap

Heap 이란?

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 자료 구조이다.
• 완전 이진 트리이기 때문에 배열을 이용하여 손쉽게 구현할 수 있다.
• max - heap은 부모가 자식보다 항상 큰 자료구조이고, min - heap 은 부모가 항상 자식보다 작은 자료 구조이다.
• 이를 응용하여 우선 순위 큐를 구현할 수 있다.
• 새로운 원소가 삽입 될 때나 root 원소를 추출하고 나서 heap 규칙을 따르도록 원소의 위치를 바꾸는 과정을
  heapify 라 불리며 log n 이 소요 된다.
• 새로운 원소는 항상 힙 구조의 제일 끝 원소로 추가되며 heapify 과정을 통해 자신의 자리를 찾아 올라가고,
  root 값인 min, max 값을 뽑고서는 제일 끝 원소를 root으로 옮기고 heapify를 진행하며 내려간다.
• BST 와 다르게 노드가 같은 레벨이어도 크기를 알 수 없다. 단지 부모보다 큰지 작은지만을 따져서 위치가 정해지기 때문인다.
• max-heap 구조일 때, heapify 함수는 아래와 같다.

Heap Sort

void heapify(int arr[], int idx, int heapSize){
    int nextIdx = idx*2;
    if(nextIdx > heapSize){
        return;
    }
    if(nextIdx + 1 <= heapSize){
        if(arr[nextIdx] < arr[nextIdx+1]){
            nextIdx += 1;
        }
    }
 
    if(arr[nextIdx] > arr[idx]){
        int tmp = arr[idx];
        arr[idx] = arr[nextIdx];
        arr[nextIdx] = tmp;
 
        heapify(arr, nextIdx, heapSize);
    }
}
 
void heapSort(int arr[]){
    int heapSize = n;
 
    for(int i=n/2;i>0;--i){
        heapify(arr, i, n);
    }
 
    while(heapSize > 0){
        int tmp = arr[1];
        arr[1] = arr[heapSize];
        arr[heapSize] = tmp;
        --heapSize;
 
        heapify(arr, 1, heapSize);
    }
}

• 배열과 min, max heap 개념을 이용해서 힙 정렬을 구현 할 수 있다.
• in-place 기법이며 공간복잡도는 O(n) 이다.
• 힙 자료구조 특성에서의 부모와 자식관계는 배열의 인덱스로 나타날 수 있다.
• 힙 자료구조가 완전이진트리의 특성을 지니기 때문에 가능하며, 부모 인덱스가 i라면 왼쪽 자식은 2*i, 오른쪽 자식은 2*i + 1이다.
  ( 따라서 배열의 인덱스는 항상 1부터 시작하여야 하며, arr[1]이 루트가 된다. )
• heapify 함수가 logn 소요 되고, n개의 배열을 정렬하여야 하기 때문에 총 시간 복잡도는 n log n이 된다.
• 힙 규칙을 만족하는 트리가 완성되면, 루트서 부터 출력하거나 원래 배열로 옮기면서 pop 해주고,
  다시 heapify가 호출하면서 순서대로 정렬할 수 있다.