[C] 우선순위 큐(Heap) 및 Heap Sort 구현

Heapify의 Sift Down동작과 Sift Up동작을 재귀함수로 구현함으로써, heapify, heap_push, heap_pop heap sort동작을 간결하고 아름답게 구현할 수 있었다. 참고로 코드는 Max Heap을 구현한 내용이다. Min Heap은 각 heapify 함수에서 크기비교 부호만 반대로 하면 된다.

Heapify 힙 구조 생성

Sift Down 방식 Heapify

/**
 * heapify sift down 
 *     p
 *    / \
 *   l   r
 */
void heapify(int arr[], int p_idx, int h_size)
{
        int largest = p_idx;
        int l_idx = p_idx * 2 + 1;
        int r_idx = p_idx * 2 + 2;

        /* find a largest one in p,l,r */
        if (l_idx < h_size && arr[l_idx] > arr[largest])
                largest = l_idx;
        if (r_idx < h_size && arr[r_idx] > arr[largest])
                largest = r_idx;
        if (largest != p_idx) { /* base case */
                swap(arr, largest, p_idx); /* swap with larger child */
                heapify(arr, largest, h_size); /* heapify agrain from the child */
        }
}

void build_heap(int arr[], int h_size)
{
        for (int i = (h_size / 2) - 1; i >= 0; i--)
                heapify(arr, i, h_size);
}

build_heap 에서 for문이 (h_size / 2) - 1 부터 시작하는 이유. leaf 노드는 heapify sift down을 할 필요가없다. 그래서 자식노드를 가지는 첫번째 노드의 인덱스부터 배열의 인덱스를 하나씩 줄여가면서 heapify를 한다. build_heap의 시간복잡도는 O(N)이다.

참고 heapify()함수 if문에서l_idx < h_size 를 먼저 체크하지 않으면, arr[]에 배열의 인덱스를 넘어가는 값을 참고할 수 있다. if (arr[l_idx] > arr[largest] && l_idx < h_size) 이렇게 구현하면 런타임 에러가 발생한다. 반드시 && 하기 전에 먼저 체크하기.

Heap Pop

int heap_pop(int arr[])
{
        int p_idx = 0;
        int ret = arr[p_idx];

        /* swap last to p_idx */
        arr[p_idx] = arr[heap_size - 1];
        heap_size--;
        /* heapify */
        heapify(arr, p_idx, heap_size);
        return ret;
}

Heap Push

heap push를 통해 추가된 값은 배열의 맨 끝(트리의 leaf)에 추가되므로, heapify동작은 루트노드부터 시작되는 sift down이 아니라 리프 노드 부터 시작되는 sift up이 되어야한다. 그래서 heapify_siftup() 함수를 아래와 같이 구현함.

void heapify_siftup(int arr[], int curr_idx)
{
        int p_idx = (curr_idx - 1) / 2;

        if (curr_idx < 1)
                return;
        if (arr[curr_idx] > arr[p_idx]) {
                swap(arr, curr_idx, p_idx);
                heapify_siftup(arr, p_idx);
        }
}

void heap_push(int arr[], int val)
{
        /* insert to the last */
        arr[heap_size] = val;
        heap_size++;
        /* heapify from the last one */
        heapify_siftup(arr, heap_size - 1);
}

Heap Sort

heapify를 구현했으면 Sort는 이제 식은 죽 먹기다. build_heap을 하면 배열의 0번 인덱스는 가장 큰값인데, 이를 배열의 맨 뒤로 swap하고, 배열의 크기를 1씩 줄여서 또다시 heapify하고 위의 내용을 반복하면. 작은 값부터 순차적으로 배열이 오름차순 정렬된다. 쉽게 이야기해서 heap pop을 수행한 뒤, 그 값을 배열의 가장 마지막부터 저장하는것과 크게 차이가 없다. (Max Heap의 경우)

heapify() 함수 하나로 build heap, Push, Pop, Sort 까지 너무나도 쉽게 구현을 할수 있다. 이 얼마나 은혜로운 코드인가 ㅜㅜ

void heap_sort(int arr[])
{       
        build_heap(arr, heap_size);
        for (int last_idx = heap_size - 1; last_idx >= 0; last_idx--) {
                swap(arr, 0, last_idx);
                heapify(arr, 0, last_idx);
        }
}

main() 함수

상단 초기화 코드

#include <stdio.h>
#define ARR_SIZE 10

int arr[ARR_SIZE] = {4,1,5,7,10,9,2,3,8,6};
int arr2[2] = {3,7};
int heap_size;

void swap(int arr[], int a, int b)
{
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
}

main() 함수

void print_arr(int arr[], int size)
{
        for (int i = 0; i < size; i++)
                printf("%d ", arr[i]);
        printf("\n");
}

int main(int argc, char *argv[])
{
        heap_size = ARR_SIZE;

        /* heapify */
        print_arr(arr, heap_size);
        build_heap(arr, heap_size);
        print_arr(arr, heap_size);

        /* heap pop */
        printf("(%d)\n", heap_pop(arr));
        print_arr(arr, heap_size);
        printf("(%d)\n", heap_pop(arr));
        print_arr(arr, heap_size);

        /* heap push */
        heap_push(arr, 11);
        print_arr(arr, heap_size);
        heap_push(arr, 12);
        print_arr(arr, heap_size);
        heap_push(arr, 9);
        print_arr(arr, heap_size);
        heap_push(arr, 10);
        print_arr(arr, heap_size);

        /* heap sort */
        heap_sort(arr);
        print_arr(arr, heap_size);
        
        return 0;
}                        

References

• heapify sift down 재귀함수 참고 https://www.programiz.com/dsa/heap-sort
• heapify 동작을 이해하기 쉽게 설명 (영상)https://youtu.be/JBHCJA2B_ss
• Heap의 sift up과 sift down 에 대해서
  https://leeminju531.tistory.com/33