[Sorting] 4. Heap, Heapify, Heap Sort

Heap Sort

Space-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다.

Time-Complexity = O(n log n)

원리

heap 자료구조를 활용할 Sorting 방법에는 두 가지 방법이 존재한다. 하나는 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 원리로 Sorting을 하게 되는 방법이고, 나머지 하나는 기존의 배열을 heapify(heap으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법이다.

Heap 자료구조란?

자료구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree 이다. 배열에 트리의 값들을 넣어줄 때, 0번째는 건너뛰고 1부터 루트노드가 시작된다. 이는 노드의 고유번호 값과 배열의 index를 일치시켜 혼동을 줄이기 위함이다. 힙에는 최소힙(min heap), 최대힙(max heap) 두 종류가 있다. Max Heap이란, 각 노드의 값이 children 의 값보다 크거나 같은 complete binary tree를 말한다. ( min heap은 그 반대이다. )

Max heap에서는 Root node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complextiry이 O(1)이다. 그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. (즉, random access가 가능하다. Min heap 에서는 최소값을 찾는데 소요되는 연산의 time complexity가 O(1)이다. )

배열에 저장하였을 때의 장점을 살리기 위해서는 인덱스 값을 알아야 한다. 어떻게 알아낼 수 있을까. 

complete binary tree는 노드의 개수가 n개 일 때, i번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.

Heapify

두 개의 subtree가 max-heap 이라고 가정할 때 root에 추가된 노드를 포함한 전체가 heap을 만족하도록 각 노드들의 위치를 조정하는 과정을 말한다. min-heap인 경우에도 마찬가지로 적용된다. max-heap의 경우에는 루트에서 작은 값이, min-heap에서는 큰 값이 트리 구조를 따라 흘러내려가면서 처리되는 방식(float-down)으로 진행된다.

max-heapify는 root node의 값이 child node의 값보다 작으면 두 개의 child node 중 값이 큰 노드와 root를 교체하고, 이 과정을 교체할 노드가 없을 때까지 (처음에 root였던 노드가 leaf node로 될 때까지) 반복해주면 된다. 이와 마찬가지로 min-heapify는 root node의 값이 child node의 값보다 크면 두 개의 child node 중 값이 작은 노드와 root를 교체하고, 이 과정을 교체할 노드가 없을 때까지 반복해주면 된다.

최대값 / 최소값 추출

최대값의 추출을 구현하려면 어떻게 하는가?

Max Heap에서 최대값은 루트 노드이다. 즉, 최대값을 추출하는데는 O(1)의 시간이 소요되는 것이다. 하지만 이게 다가 아니라 루트 노드가 사라진 다음에도 트리는 Max Heap을 만족해야 한다. 즉, max-heapify를 해줘야 하는 것이다. 배열을 기반하였기 때문에 인덱스로 접근하여 heap 에서 가장 마지막 원소와 root를 swap해준 뒤, 총 배열의 size가 1 감소된 상태에서 heapify 를 해준다. 이 과정은 노드 한 개에 대해서 heapify를 진행하는 것이므로 <big-O(log n)>이 된다. 최대값을 추출하는 과정을 배열의 모든 원소에 시행하게 되면 오름차순으로 정렬이 된다.

최소값의 추출을 구현하려면 어떻게 하는가?

Min Heap에서 최소값은 루트노드이다. 즉 최소값을 추출하는데 O(1)의 시간이 소요되는 것이다.

최대값 추출 과정과 동일하다. 이 최소값 추출하는 과정을 배열의 모든 원소에 시행하게 되면 내림차순으로 정렬이 된다.

새로운 값 삽입

heap에 새로운 값이 삽입되는 경우에는 어떤 조치를 취해줘야 heap의 형태가 유지될 수 있을까?

Max heap에 새로운 node가 추가된 상황에서는 일단 새로 들어온 노드의 값이 제일 작다고 가정하자. 그리고 배열의 제일 마지막에 삽입을 한 뒤, 부모 노드와 비교하면서, 역 heapify를 해준다.

heap에 데이터를 저장하는 시간 복잡도는 O(log n)이고, 삭제 시간 복잡도 또한 O(log n)이 된다. 때문에 힙 자료구조를 사용하여 Sorting을 하는데 time complexity는 O(log n)이 된다. 이 정렬을 하려는 대상이 n개라면 time complexity는 O(n log n)이 된다.

주어진 배열을 Heap 자료구조로 만들어 Heap Sorting을 하는 코드를 보자.

몇 가지 짚고 넘어가야 할 부분이 있다.

heap이라는 자료구조는 어떤 자료형을 포함하고 있을까?

//util - heap datastructure
typedef struct Heap{
    int size;
    int * element;
}heap_t;

heap->element에는 arr의 주소값을 대입하여 같은 arr를 가리킬 수 있게 한다. 그리고 size에는 arr의 size의 1을 뺀 값을 넣어줘야 한다. 그 이유는 heap 자료구조를 생성할 때 index와 heap을 구성하게 되는 node들의 index를 일치시키기 위해 0번째 값은 0이라는 값으로 초기화를 하기 때문에, 이와 마찬가지의 이유로 heap->size는 heap의 마지막 원소를 가리킬 수 있도록 heap->size = size - 1 로 해주는 것이다.

heapify를 해줄 때, 모든 원소에 대해서 모두 heapify를 해줘야 하는가?

그렇지 않다. 총 배열의 중간부터 해주면 된다.

그 이유는 우리가 heapify를 정의하는 부분에서 확인할 수 있다. subtree가 heap 자료구조를 만족한다는 가정하에 root node에 대해서 heapify를 진행했다. 따라서 heap->size/2 부터 0번째 index까지 heapify를 시행하면 되는 것이다.

c code>

//Heap sorting!
void heap_sort(int * arr, int size) {
    heap_t * heap = malloc(4);//makes heap!
    heap->element = arr;
    heap->size = size - 1;//heap->size에는 바로 인덱스에 접근할 수 있는 값을 넣어주자.
    
    for(int i = heap->size/2; i > 0; i--) {//heapify를 하는 것은 정체 배열 중 중간부터!
        heapify(heap, i);
    }
    for(int i = heap->size ; i >= 1; i--) {//현재 root에는 최대값이 저장되어 있다!
        swapValue(&heap->element[1], &heap->element[i]);//제일 마지막 원소와 그 위치를 바꿔준다.
        heap->size--;//최대값이 정렬됬으므로 정렬된 부분을 제외한 나머지에 대해
        heapify(heap, 1);//heapify를 시행한다.
    }
}

//max heapify!
void heapify(heap_t * heap, int idx) {
    int temp = idx;
    int * arr = heap->element;
    
    if(heap->size < idx * 2) return;//child node가 없는 경우에는 heapify가 완료됬으므로 return.
    
    if(heap->size == idx * 2) {//node의 child node가 left child node만 존재하는 경우
        if(arr[idx] < arr[idx*2])
            temp = idx*2;
    } else {//node의 child node가 left, right 두 개인 경우
        if(arr[idx*2] > arr[idx*2 + 1]){//left와 right 둘 중 큰 값에 대해 적용한다.
            if(arr[idx] < arr[idx*2])
                temp = idx*2;
        } else {
            if(arr[idx] < arr[idx*2 + 1])
                temp = idx * 2 + 1;
        }
    }
    
    if(temp != idx) {//최종적으로 temp가 변경되었다면 heapify가 더 진행되야 한다.
        swapValue(&heap->element[idx], &heap->element[temp]);
        heapify(heap, temp);
    }
}

추가적으로 최대값을 추출하거나, 새로운 값을 insert하는 경우의 코드를 살펴보자.

c code>

//delete value in root node on heap!
int heapExtractMax(heap_t * heap, int * maxvalue) {
    if(heap == NULL || heap->element == NULL) return 0;
    if(heap -> size < 1) return 0;
    
    *maxvalue = heap->element[1];
    heap->element[1] = heap->element[heap->size];
    heap->size--;
    heapify(heap, 1);
    
    return 1;
}

//max value insert into heap!
void heapIncreaseKey(heap_t * heap, int i, int key) {
    if(heap == NULL || heap->element == NULL) return;
    if(heap->element[i] > key) return;
    heap->element[i] = key;
    
    while(i>1 && heap->element[i/2] < heap->element[i]) {
        swapValue(&heap->element[i/2], &heap->element[i]);
        i = i/2;
    }
}
 
void maxHeapInsert(heap_t * heap, int key) {
    if(heap == NULL || heap->element == NULL) return;
    
    heap->size++;
    heap->element[heap->size] = INT_MIN;
    heapIncreaseKey(heap, heap->size, key);
}

4. the end