C Data Structure - 힙 정렬

오늘은 힙 정렬이다.

힙 정렬이란?

말 그대로 Heap 자료구조를 이용한 정렬 방식이다. Min Heap에서 루트 노드부터 빼오면 오름차순 정렬이 가능한 점을 이용해한 것이다.

힙 정렬은 Heap 자료 구조 조금 개조하면 만들 수 있다.
아래 그림과 같은 Min-Heap을 이용하면 정렬 성능이 죽여준다 ㅋ 

우선 순위 큐에서도 우선 순위가 높은 것을 작은 값이라고 약속하고 작성한다면 같은 결과이다. 뭐 그 기반이 heap 자료구조이니 heap을 통해서 구현했고, 이미 구현해놓은 것에 우선 순위 부분만 조금 수정하였다. 나중에 기억 안날 때에는 아래 링크 먼저 보고, 다음 코드를 확인하면 될 듯 하다. 

수정한 부분을 보자면, 원래 기존 heap 코드는 우선 순위를 결정하는 부분을 삽입마다 지정하기로 했는데 그것을 함수 포인터를 이용하여 없애버리고 자동으로 우선 순위를 나뉘도록 했다.

https://typingdog.tistory.com/110?category=924874

C Data Structure - Heap ( Priority Queue, 우선 순위 큐 ) 개념 및 코드 구현

다음은 코드이다.

코드 및 실행 결과

----

 
#include <stdio.h>
 
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
 
struct heap_element // 정수 값을 저장하는 힙의 노드 구조체로 우선 순위를 지정할 수 있다.
{
    int data;
};
typedef struct heap_element heap_element;
 
struct heap
{
    int count;
    heap_element heap_arr[HEAP_LEN]; // 힙은 배열 구조를 기반으로 구현된다.
    int (*ComparePriority)(heap_element* h1, heap_element* h2);
};
typedef struct heap heap;
 
void HeapInit(heap* h, int (*CompFunc)(heap_element* h1, heap_element* h2));
int HIsEmpty(heap* h);
void HInsert(heap* h, int data);
int HDelete(heap* h);
void ShowHeap(heap* h);
 
int GetParentIndex(int child_index);
int GetLeftChildIndex(int parent_index);
int GetRightChildIndex(int parent_index);
 
int GetChildIndex(heap* h, int parent_index);
int ComparePriority(heap_element* n1, heap_element* n2);
 
void HeapSort(int arr[], int n, int (*CompFunc)(heap_element* h1, heap_element* h2))
{
    int i = 0;
    heap h;
    HeapInit(&h, CompFunc);
 
    for (i = 0; i < n; i++)
        HInsert(&h, arr[i]);
    ShowHeap(&h);
 
    printf("\n\n\n");
    for (i = 0; i < n; i++)
        arr[i] = HDelete(&h);
    ShowHeap(&h);
 
    return;
}
 
int main(void)
{
    int arr[21] = { 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    int i = 0;
 
    HeapSort(arr, sizeof(arr) / sizeof(int), ComparePriority);
 
    printf("\n\n\n");
    for (i = 0; i < 21; i++)
        printf("%d, ", arr[i]);
    fputc('\n', stdout);
    return 0;
}
 
int ComparePriority(heap_element* n1, heap_element* n2)
{ // 앞에꺼가 크면 양수, 뒤에꺼가 크면 음수
    return (n1->data - n2->data);
}
 
void HeapInit(heap* h, int (*CompFunc)(heap_element* h1, heap_element* h2))
{
    int i = 0;
    h->count = 0;
    for (i = 0; i < HEAP_LEN; i++)
        h->heap_arr[i].data = 0;
    h->ComparePriority = CompFunc;
    return;
}
int HIsEmpty(heap* h)
{
    return (h->count == 0) ? TRUE : FALSE;
}
 
void HInsert(heap* h, int data)
{
    int insert_index = h->count + 1;
    int parent_index = 0;
    heap_element new_element = { data };
 
    while (insert_index != 1) // 처음 삽입되는 위치가 루트 노드가 아니면 혹은 갱신된 추가 인덱스가 루트 노드가 아니면
    {
        parent_index = GetParentIndex(insert_index);
        if (h->ComparePriority(&new_element, &(h->heap_arr[parent_index])) > 0) // 우선 순위가 부모가 높다면 구조 재조정이 필요 없다.
            break;
        else // 추가할 노드가 우선 순위가 높은 경우, 계속 구조 재조정이 필요함.
        {
            h->heap_arr[insert_index] = h->heap_arr[parent_index];
            insert_index = parent_index;
        }
    }
    h->heap_arr[insert_index] = new_element;
    h->count++;
    return;
}
 
int HDelete(heap* h)
{
    int r_data = h->heap_arr[1].data; // 삭제할 데이터(Pop 할 데이터와 같은 의미)
    heap_element last_element = h->heap_arr[h->count]; // 비교 대상인 마지막 노드 지정( 마지막 노드를 루트 자리로 올려 비교하기 때문 )
    // 최종 결정된 인덱스
    int parent_index = 1; // 루트 노드 부터 시작한다.
    int child_index = 0;
 
    while (child_index = GetChildIndex(h, parent_index))
    {
        if (h->ComparePriority(&last_element, &(h->heap_arr[child_index])) <= 0)// 자식 노드보다 우선 순위가 높다면 현재 구한 인덱스로의 변경만 하면 된다.
            break;
        else // 계속해서 구조의 재조정이 필요한 경우
        {
            h->heap_arr[parent_index] = h->heap_arr[child_index];
            parent_index = child_index;
        }
    }
    h->heap_arr[parent_index] = last_element;
    h->count--;
    return r_data;
}
// Heap의 내용을 트리의 계층(레벨) 별로 보여준다.
void ShowHeap(heap* h)
{
    int begin = 1, end = 1, index = 1;
    int i = 0;
 
    if (h->count == 0)
    {
        printf("heap이 비었습니다!\n");
        return;
    }
 
    printf("%d, \n", h->heap_arr[1].data);
 
    while (index <= h->count)
    {
        begin = GetLeftChildIndex(begin), end = GetRightChildIndex(end); // 각 레벨 층의 시작과 끝 인덱스 설정 후 출력한다
        if (end > h->count)    end = h->count; // end가 마지막 노드보다 넓은 범위에 있다면 end를 마지막 노드의 인덱스로 설정
 
        index = end + 1; // 위에서 지정한 end 다음 값으로 변경한다.
 
        for (i = begin; i <= end; i++)
            printf("%d, ", h->heap_arr[i].data);
        fputc('\n', stdout);
    }
    return;
}
 
// 부모 노드의 인덱스를 구한다.
int GetParentIndex(int child_index)
{
    return child_index / 2;
}
// 왼쪽 자식 노드의 인덱스를 구한다.
int GetLeftChildIndex(int parent_index)
{
    return parent_index * 2;
}
// 오른쪽 자식 노드의 인덱스를 구한다.
int GetRightChildIndex(int parent_index)
{
    return (parent_index * 2) + 1;
}
// 두 자식 노드 중 우선 순위에 따라 반환한다.
int GetChildIndex(heap* h, int parent_index)
{
    if (GetLeftChildIndex(parent_index) > h->count) // 자식 노드가 없으면 0 반환
        return 0;
    else if (GetLeftChildIndex(parent_index) == h->count) // 자식 노드가 하나인 경우에는 해당 인덱스 반환
        return GetLeftChildIndex(parent_index);
    else // 두 자식 노드 중 우선 순위가 높은 것의 인덱스 반환
    {
        int left_child_index = GetLeftChildIndex(parent_index), right_child_index = GetRightChildIndex(parent_index);
        if (h->ComparePriority(&(h->heap_arr[left_child_index]), &(h->heap_arr[right_child_index])) > 0)// 오른쪽 자식 노드가 더 우선 순위가 높다면
            return right_child_index; // 오른쪽 자식 노드의 인덱스 반환
        else // 왼쪽 자식 노드가 더 우선 순위가 높거나 양쪽 노드의 우선 순위가 같다면
            return left_child_index; // 왼쪽 자식 노드의 인덱스 반환
    }
}
 

----

 

힙 정렬 성능

힙 데이터 저장 시간 복잡도 : O(log2 n) - 2는 아래 첨자의 2이다.
힙 데이터 삭제 시간 복잡도 : O(log2 n) - 2는 아래 첨자의 2이다.
힙 데이터 정렬의 경우, 저장과 삭제를 각각 n번씩 수행하므로 시간 복잡도 : O(n log 2 n) - 2는 아래 첨자의 2이다.

힙 구조에 데이터 삽입, 삭제 등이 이루어진다는 것을 고려한다고 하더라도, 앞서 봤던 O(n^2) 정렬들 보다도 성능이 좋은 것이다.