Heap Sort

최소 힙(min heap)을 이용하여 오름차순 정렬을 구현할 수 있다.
최소 힙의 정의는 다음과 같다.

완전 이진 트리로 구성되고, 항상 부모 노드의 키값은 양쪽 자식 노드의 키값보다 작은 트리.

최대 힙은 반대로 정의할 수 있다.
결국 최소 혹은 최대 힙은 항상 루트 노드에 노드 중에서 가장 작은 혹은 가장 큰 키 값을 가지고 있게 된다.
그 점을 이용해서 오름차순 혹은 내림차순으로의 정렬을 할 수가 있는데 이를 힙 정렬이라고 한다.
오늘 소개할 코드는 최소 힙을 기준으로 오름차순 정렬을 하는 코드이다.
코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

#pragma warning(disable:4996)

#define MAX_HEAP_SIZE 4096
#define TRUE          1
#define FALSE         0


typedef struct _HEAP_NODE {
    int key;
} HEAP_NODE;

typedef struct _HEAP {
    int size;
    struct _HEAP_NODE *heap;
} HEAP;


void heap_Initialize(HEAP *h);
void heap_Insert(HEAP *h, int key);
void heap_Build(HEAP *h);
void heap_SiftDown(HEAP *h, int i);
void heap_Swap(HEAP_NODE *dst, HEAP_NODE *src);
int heap_Delete(HEAP *h);


int main() {
    HEAP h;
    int tmp_key;

    heap_Initialize(&h);

    printf("insert key (-1: end of insert)\n");
    while (TRUE) {
        printf("key => ");
        scanf("%d", &tmp_key);
        if (tmp_key == -1) {
            break;
        } else {
            heap_Insert(&h, tmp_key);
        }
    }

    printf("\n=======================================\n");
    printf("total input: %d\n", h.size);
    printf("Ascending order Sort Result:\n");
    while (TRUE) {
        if (h.size == 0) {
            break;
        } else {
            printf("%d ", heap_Delete(&h));
        }
    }
    printf("\n");

    free(h.heap);

    return 0;
}

void heap_Initialize(HEAP *h) {
    h->heap = (HEAP_NODE *) malloc(sizeof(HEAP_NODE) * MAX_HEAP_SIZE);
    if (h->heap == NULL) {
        fprintf(stderr, "Memory allocation error: heapInitialize()\n");
        return;
    }

    h->size = 0;
}

void heap_Insert(HEAP *h, int key) {
    h->size++;
    h->heap[h->size].key = key;
    heap_Build(h);
}

void heap_Build(HEAP *h) {
    int i;

    for (i = h->size / 2; i >= 1; i--) {
        heap_SiftDown(h, i);
    }
}

void heap_SiftDown(HEAP *h, int i) {
    int child;
    HEAP_NODE siftKey;
    int parent = i;
    int found = FALSE;

    siftKey = h->heap[i];
    while ((2 * parent <= h->size) && !found) {
        if ((2 * parent < h->size) && (h->heap[2 * parent].key > h->heap[2 * parent + 1].key)) {
            child = 2 * parent + 1;
        } else {
            child = 2 * parent;
        }

        if (siftKey.key > h->heap[child].key) {
            h->heap[parent] = h->heap[child];
            parent = child;
        } else {
            found = TRUE;
        }
    }

    h->heap[parent] = siftKey;
}

void heap_Swap(HEAP_NODE *dst, HEAP_NODE *src) {
    int swap_key = dst->key;

    dst->key = src->key;
    src->key = swap_key;
}

int heap_Delete(HEAP *h) {
    int min;

    min = h->heap[1].key;
    heap_Swap(&h->heap[1], &h->heap[h->size]);
    h->size--;
    heap_Build(h);

    return min;
}

정렬을 할 데이터를 순차적으로 힙에 집어넣고 최소 힙을 만든 후에, 힙에서 루트 노드를 제거하면서 정렬하는 방법이다.

이 코드에서 가장 눈여겨 볼 것은 heap_SiftDown() 함수이다.
사실 힙을 만들어가는 과정은 위의 코드보다 훨씬 더 간단하게 작성할 수도 있다.
새로 추가할 노드를 트리의 가장 마지막에 붙인 후에 순서대로 부모 노드와의 키값을 비교해서 swap해주면서 루트노드까지 올라가면 힙이 된다.
그러나, 그렇게 코드를 작성할 경우에는 swap을 최악의 경우에 트리의 높이만큼 해 줘야 하는 경우가 발생하게 된다.
이런 비효율적인 것을 방지하기 위해, siftdown 함수를 사용한다.
계속 바꾸면서 올라가지 않고, 키값의 비교만을 수행하고, 새로 추가된 노드가 들어가야 할 자리를 찾아가는 방식이다.
사실 힙 트리에서 새로운 노드가 추가되기 전까지는 힙 트리를 유지하고 있기 때문에 가능한 방법이다.
또한 힙에서는 인덱스를 가지고 부모 노드와 왼쪽 자식 노드, 오른쪽 자식 노드를 금방 찾아갈 수 있다.
힙에서 이것이 굉장히 중요하게 작용한다.
일반적으로 n 번째 노드의 부모와 각 자식 노드는 다음과 같이 정의된다.
부모 노드: n/2
왼쪽 자식 노드: 2n
오른쪽 자식 노드: 2
n +1
*이러한 구성 원리로 인해 힙에서 0번째 인덱스는 사용하지 않는다.

위 코드의 샘플 인풋과 결과는 다음과 같다.

댓글 남기기