Heap

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MALLOC(p, s)                            \
    if (!((p) = (nodePointer)malloc(s)))        \
    {                                           \
        fprintf(stderr, "Insufficient Memory"); \
        exit(EXIT_FAILURE);                     \
    }
#define MAX_ELEMENTS 200 /* maximum heap size+l */
#define HEAP_FULL(n) (n == MAX_ELEMENTS - 1)
#define HEAP_EMPTY(n) (!n)

typedef struct
{
    int key;
    char name[20];
    char address[100];
} element;
element heap[MAX_ELEMENTS];


typedef struct node *nodePointer;
typedef struct node
{
    nodePointer leftChild;
    element data;
    nodePointer rightChild;
} node;

void insert(int *current_size_ptr);
element deletion(int *current_size_ptr);
void search(int current_size);

int main()
{
    int current_size = 0;
    char option = 0;
    element check;
    while (1)
    {
        if (option != '\n')
            printf("i(삽입),d(삭제),r(전체읽기),q(작업 종료)를 선택하세요:");
        scanf("%c", &option);
        switch (option)
        {
        case 'i':
            insert(&current_size);
            break;
        case 'r':
            search(current_size);
            break;
        case 'd':
            check = deletion(&current_size);
            printf("<학번, 이름, 주소> =<%d,%s,%s>\n ", check.key, check.name, check.address);
            break;
        case 'q':
            break;
        }
        if (option == 'q')
            break;
    }
    return 0;
}

void insert(int *current_size_ptr)
{
    int i;
    element item;
    printf("삽입할 자료(학번, 이름, 주소)를 입력하시오:");
    scanf("%d", &item.key);
    scanf("%s", item.name);
    fgets(item.address, 100, stdin);
    if (item.address[strlen(item.address) - 1] == '\n')
    {
        item.address[strlen(item.address) - 1] = 0;
    }

    if (HEAP_FULL(*current_size_ptr))
    {
        fprintf(stderr, "The heap is full. \n");
        exit(EXIT_FAILURE);
    }
    i = ++(*current_size_ptr);
    while ((i != 1) && (item.key > heap[i / 2].key))
    {
        heap[i] = heap[i / 2];
        i /= 2;
    }
    heap[i] = item;
}

element deletion(int *current_size_ptr)
{
    int parent, child;
    element item, temp;
    if (HEAP_EMPTY(*current_size_ptr))
    {
        fprintf(stderr, "The heap is empty\n");
        exit(EXIT_FAILURE);
    }
    /* save value of the element with the highest key */
    item = heap[1]; // heap[0]이 아니고 heap[1]이 root node이다.
    /* use last element in heap to adjust heap */
    temp = heap[(*current_size_ptr)--];
    parent = 1;
    child = 2;
    while (child <= *current_size_ptr)
    {
        /* find the larger child of the current parent */
        if ((child < *current_size_ptr) && (heap[child].key < heap[child + 1].key))
            child++;
        if (temp.key >= heap[child].key)
            break;
        /* move to the next lower level */
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return item;
}

void search(int current_size)
{
    int current, i;
    current = 1;
    for (i = current; i <= current_size; i++)
    {
        printf("<학번, 이름, 주소> =<%d,%s,%s>\n", heap[i].key, heap[i].name, heap[i].address);
    }
}

/*
i
30 ohseungmin dague
i
60 seosanghee kyung san
i
20 choijaewoong manchon
i
50 someone somewhere
i
80 ohseungmin dague
i
90 seosanghee kyung san
i
41 choijaewoong manchon
i
53 someone somewhere
i
37 ohseungmin dague
i
69 seosanghee kyung san
i
45 choijaewoong manchon
i
52 someone somewhere
i
38 ohseungmin dague
i
68 seosanghee kyung san
i
48 choijaewoong manchon
i
58 someone somewhere
i
36 ohseungmin dague
i
66 seosanghee kyung san
i
46 choijaewoong manchon
i
55 someone somewhere
r
d
d
r
q
*/

 

 

자료 출처 : gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

 

 

힙

• 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조.
• 최댓값 또는 최솟값을 추출하기에 굉장히 효율적인 자료구조.

힙은 일차원 배열에서 구현하는 것이 연결 리스트보다 효율적이다.

배열에서 인덱스를 활용해서 데이터를 이진트리처럼 구조화하는 것이다.

위 사진처럼 배열의 마지막에 데이터가 추가되고, 추가된 데이터는 부모 노드와 비교하여 자리를 바꾸는 것을 반복한다.

 

 

이러한 힙은 정렬의 수단으로도 쓰인다.

힙 정렬의 방식은,

최댓값이 들어있는 루트노드(배열 인덱스 1)의 데이터를 추출해서 배열의 맨 끝부터 차례대로 채워넣는다.

 

나는 힙 트리를 상상할때 항상 이진트리로 상상했다.

적어도 나는

힙 트리의 작동방식을 이해하려면 힙이 트리모양을 하고있다는 것보단

힙이 애초에 배열이라는 것을 인정하는게 더 이해하기 쉬웠던 것 같다.

 

힙은 트리구조이고, 배열에서의 인덱스를 활용해 구현했다 뭐 이렇게 상상하니

배열의 중간중간이 비어있을거라 생각하게 되는 것 같다. 

 

www.youtube.com/watch?v=kPRA0W1kECg

중간에 heap sort의 작동방식도 나오는데 아주 직관적이다.