[C/정렬] 힙정렬(2) HeapSort: 배열과 이진트리 활용: 간결화

// heapSort_choice.c
// 배열과 이진트리를 활용한 힙정렬
// 참고 유튜브 영상: "초이스 프로그래밍"채널의 "[자료구조] 힙 트리/힙 정렬 : 개념과 구현(C언어)"
// 강의에 나온 내용을 그대로 코드로 작성한 것.
// 이 코드의 핵심은 "왼쪽 노드를 따라 내려가며 값을 비교해서 값을 교환한다"이다. 
// 왜 왼쪽 노드를 따라 내려가며 값을 비교해야 하는가를 이해하는 게 핵심이다.
// 그리고 자식 노드를 child 포인터로 지적하면서 직관적이고 효율적으로 교환 작업을 하고 있다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_COUNT 100

typedef struct {
    int data[MAX_COUNT];
    int size;
} heapType;

// 힙에 데이터를 넣는다. 성공 시 해당 데이터의 index 반환
int insertHeap(heapType *h, int item) {
    int index, tmp;
    if (h->size >= (MAX_COUNT - 1)) {
        printf("Full!!\n");
        return -1;  
    }
    h->size++;
    index = h->size;
    h->data[index] = item;

    while (h->data[index / 2] < h->data[index] && index != 1) {
        tmp = h->data[index];
        h->data[index] = h->data[index / 2];
        h->data[index / 2] = tmp;
        index = index / 2;
    }
    return index;
}

int removeHeap(heapType *h) {
    int cur, tmp, child;

    int topData = h->data[1];
    if (h->size == 0) {
        printf("Empty!\n");
        return -1;
    }
    
    h->data[1] = h->data[h->size];
    h->size -= 1;

    cur = 1;
    //스톱 조건; 왼쪽 자식이 없을 때(오른쪽 자식도 없다는 뜻이므로)
    //스톱 조건2: 자식들의 값이 cur보다 작을 때 (이미 정렬되어 있다는 뜻)
    while (cur * 2 <= h->size) {
        child = cur * 2;
        if (child + 1 <= h->size && h->data[child] < h->data[child+1]) {
            child = child + 1;
        }
        if (h->data[child] <= h->data[cur]) break;
        // 부모 자식간 값 교환
        tmp = h->data[cur];
        h->data[cur] = h->data[child];
        h->data[child] = tmp;
        
        cur = child;
    }
    return topData;
}

int printTree(heapType *h) {
    int i;
    for (i = 1; i <= h->size; i++) {
        printf("%d  ", h->data[i]);
    }
    printf("\n");
    return --i;
}

void main() {
    heapType heap;
    heap.size = 0;
    int i, count;

    int array [] = {17, 29, 27, 15, 34, 43, 12, 24, 33, 37, 51};

    // 파이썬에서 np.random.randint(1, 10000, 50) 으로 생성한 난수들
    /*int array[50] = { 2349,  690, 1207, 9595, 8611, 3203, 9586, 2098, 1853, 3951, 6640,
       4757, 3249,  488, 8033, 4511, 1805, 9620, 5983, 1608, 6120, 9157,
       2917, 8367,  842, 2240, 8623, 7582, 9602, 5173, 8015, 7252, 4591,
       2328, 9141, 1047, 7268, 5560, 4738, 2591, 3416, 4020, 4139,  708,
       8489, 8956, 7097, 1646, 6331, 8425 };*/

    int size = sizeof(array) / sizeof(int);

    for (i = 0; i < size; i++ ) {
        insertHeap(&heap, array[i]);
    }
    printTree(&heap);

    count = heap.size;
    for (i = 0; i < count/2; i++) {
        printf("removed: %d\n", removeHeap(&heap));
        printTree(&heap);
        printf("Now, size of the heap is %d.\n", heap.size);
        printf("------------------------------------\n");
    }
    printf("Now, size of the heap is %d.\n", heap.size);

    return 0;
}

----------실행 결과----------
1  43  34  29  37  27  12  15  24  17  33  
removed: 51
43  37  34  29  33  27  12  15  24  17  
Now, size of the heap is 10.
------------------------------------
removed: 43
37  33  34  29  17  27  12  15  24  
Now, size of the heap is 9.
------------------------------------
removed: 37
34  33  27  29  17  24  12  15  
Now, size of the heap is 8.
------------------------------------
removed: 34
33  29  27  15  17  24  12  
Now, size of the heap is 7.
------------------------------------
removed: 33
29  17  27  15  12  24  
Now, size of the heap is 6.
------------------------------------
Now, size of the heap is 6.