[자료구조] HEAP c

힙 구성c

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

#pragma warning (disable : 4996)

typedef struct heap
{
    int* arr; //힙을 구성할 배열
    int capacity; //배열의 최대 크기
    int size; //저장된 원소의 개수
}heap;

void createHeap(heap* p, int count);
void insert(heap* p, int value);
void display(int* arr, int size);
void shiftUp(int* arr, int childIdx);
int extractMax(heap* p);

int main()
{
    heap hp;
    int count;
    printf("힙의 크기 입력: ");
    scanf("%d", &count);

    createHeap(&hp, count);

    insert(&hp, 4);
    insert(&hp, 2);
    insert(&hp, 8);
    insert(&hp, 5);
    insert(&hp, 1);
    insert(&hp, 99);
    insert(&hp, 12);
    insert(&hp, 880);
    insert(&hp, 88);
    insert(&hp, 55);
    insert(&hp, 1000);

    printf("힙구조로 변환 된 배열: ");
    display(hp.arr, hp.size);

    printf("최댓값 : %d\n", extractMax(&hp)); //힙에서 삭제라는 건 최댓값을 뽑아내겠다. 무조건 배열의 첫 번째 값만 삭제한다.
    printf("최댓값 : %d\n", extractMax(&hp)); //힙에서 삭제라는 건 최댓값을 뽑아내겠다. 무조건 배열의 첫 번째 값만 삭제한다.
    printf("최댓값 : %d\n", extractMax(&hp)); //힙에서 삭제라는 건 최댓값을 뽑아내겠다. 무조건 배열의 첫 번째 값만 삭제한다.
    printf("최댓값 : %d\n", extractMax(&hp)); //힙에서 삭제라는 건 최댓값을 뽑아내겠다. 무조건 배열의 첫 번째 값만 삭제한다.
    printf("최댓값 : %d\n", extractMax(&hp)); //힙에서 삭제라는 건 최댓값을 뽑아내겠다. 무조건 배열의 첫 번째 값만 삭제한다.

    free(hp.arr); //동적으로 할당 된 배열을 제거
    return 0;
}

void createHeap(heap* p, int count)
{
    p->arr = (int*)malloc(sizeof(int)*count);
    p->capacity = count;
    p->size = 0;
}
void shiftUp(int* arr, int childIdx)
{
    int parentIdx = (childIdx - 1) / 2;
    int temp;

    if(childIdx != 0 && arr[childIdx] > arr[parentIdx])
    {
        // 값 교환
        temp = arr[childIdx];
        arr[childIdx] = arr[parentIdx];
        arr[parentIdx]= temp;
        //재귀호출(교환된 값을 가지고 재귀 호출)
        shiftUp(arr,parentIdx);
    }
}

void insert(heap* p, int value)
{
    if(p->size == p->capacity)
    {
        printf("\n\n\t\t 저장 공간이 부족해서 더 이상 저장할 수 없습니다.\n");
        printf("\t\t삭제 후 다시 저장하세요\n");
        return;
    }
    p->arr[p->size] = value;
    //shiftUp: 자식 노드 입장에서 부모 노드와 비교
    shiftUp(p->arr, p->size);

    p->size++;
}

void display(int* arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    puts("");
}

void shitfDown(int* arr, int parentIdx, int size)
{
    int leftIdx = 2 * parentIdx + 1;
    int rightIdx = leftIdx + 1;
    int largeIdx = -1; // 자식 노드가 없는 경우를 방지하기 위해서
    int temp;

    if(leftIdx < size)
        largeIdx = leftIdx;

    if(rightIdx < size && arr[leftIdx] < arr[rightIdx])
        largeIdx = rightIdx;

    // largeIdx != -1 => leftIdx와 rightIdx가 모두 범위를 벗어남
    if(largeIdx != -1 && arr[largeIdx] > arr[parentIdx]) // 자식 노드 중 큰 값과 부모 노드의 값을 비교
    {
        //값 교환
        temp = arr[largeIdx];
        arr[largeIdx] = arr[parentIdx];
        arr[parentIdx] = temp; //값 교환

        shitfDown(arr, largeIdx, size);
    }
}

int extractMax(heap* p)
{
    //1. 배열의 마지막 값을 첫 번째 값으로 대체
    int delValue = p->arr[0];
    p->arr[0] = p->arr[p->size - 1];
    p->size--; //원소의 개수 감소

    //shiftDown : 부모 노드 입장에서 자식 노드의 값을 구해 비교
    shitfDown(p->arr, 0, p->size);
    return delValue; //첫 번째 값 리턴
}

Heapify

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

#pragma warning (disable : 4996)

#define ARR_SIZE 10

void shiftDown(int* arr, int parentIdx, int size);

//shiftDown : 부모 노드가 자식 노드의 값을 구해 비교
void shiftDown(int* arr, int parentIdx, int size)
{
    //최소힙
    int leftIdx = 2 * parentIdx + 1;
    int rightIdx = leftIdx + 1;
    int smallIdx = -1; // 자식 노드가 없는 경우를 방지하기 위해서
    int temp;

    if(leftIdx < size)
        smallIdx = leftIdx;

    if(rightIdx < size && arr[leftIdx] > arr[rightIdx])
        smallIdx = rightIdx;

    // largeIdx != -1 => leftIdx와 rightIdx가 모두 범위를 벗어남
    if(smallIdx != -1 && arr[smallIdx] < arr[parentIdx]) // 자식 노드 중 큰 값과 부모 노드의 값을 비교
    {
        //값 교환
        temp = arr[smallIdx];
        arr[smallIdx] = arr[parentIdx];
        arr[parentIdx] = temp; //값 교환

        shiftDown(arr, smallIdx, size);
    }
}

void display(int* arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    puts("");
}

void heapify(int* arr, int size) //O(logN)
{
    for(int i = size / 2 - 1; i >= 0; i--) //부모의 인덱스
    {
        shiftDown(arr, i, size); //저장된 원소의 개수 / 2 만큼 shiftDown
    }
}

int main()
{
    int arr[10] = {6, 4, 8, 7, 5, 1, 3, 2, 10, 9};

    printf("Original array:");
    display(arr, 10);

    heapify(arr, 10); //배열, 배열에 저장된 개수

    printf("heapify arrary: ");
    display(arr, 10);

    printf("배열의 최솟값은 %d입니다\n", arr[0]);

    return 0;
}

힙 정렬 c

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

#pragma warning (disable : 4996)

#define ARR_SIZE 10

void shiftDown(int* arr, int parentIdx, int size);
void heapSort(int* arr, int size);
void display(int* arr, int size);

//shiftDown : 부모 노드가 자식 노드의 값을 구해 비교
void shiftDown(int* arr, int parentIdx, int size)
{
    //최소힙
    int leftIdx = 2 * parentIdx + 1;
    int rightIdx = leftIdx + 1;
    int largeIdx = -1; // 자식 노드가 없는 경우를 방지하기 위해서
    int temp;

    if(leftIdx < size)
        largeIdx = leftIdx;

    if(rightIdx < size && arr[leftIdx] < arr[rightIdx])
        largeIdx = rightIdx;

    // largeIdx != -1 => leftIdx와 rightIdx가 모두 범위를 벗어남
    if(largeIdx != -1 && arr[largeIdx] > arr[parentIdx]) // 자식 노드 중 큰 값과 부모 노드의 값을 비교
    {
        //값 교환
        temp = arr[largeIdx];
        arr[largeIdx] = arr[parentIdx];
        arr[parentIdx] = temp; //값 교환

        shiftDown(arr, largeIdx, size);
    }
}

//힙 정렬 시간 복잡도 : O(N * logN)
void heapSort(int* arr, int size)
{
    // 1. 최대힙으로 만들어야 한다. => O(logN) => 원소의 개수 / 2 반복
    for(int i = size / 2 -1; i >= 0; i--) //parentIdx의 첨자
        shiftDown(arr, i, size);

    // 2. 첫 번째 값과 마지막 값부터 교환 => O(N)
    for (int i = 9; i >= 1; i--)
    {
        int temp= arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        //0번째 원소에 힙구조에 맞지 않는 값이 들어가 있기 때문이다.
        shiftDown(arr, 0, i);
    }

    /*
    //첫번째 값 <-> 마지막 값
    int temp = arr[0];
    arr[0] = arr[9];
    arr[9] = temp;

    //첫번째 값 <-> 마지막 값
    int temp = arr[0];
    arr[0] = arr[8];
    arr[8] = temp;
    ...
    */
}

void display(int* arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    puts("");
}

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

    printf("Original array:");
    display(arr, 10);

    heapSort(arr, 10); //배열, 배열에 저장된 개수

    printf("Sorted arrary: ");
    display(arr, 10);

    return 0;
}

K번째 큰 값찾기

#include <stdio.h>
#include <stdlib.h> // malloc, free
#include <string.h> // memcpy

#pragma warning (disable : 4996)

#define ARR_SIZE 10

void shiftDown(int* arr, int parentIdx, int size);
void heapSort(int* arr, int size);
void display(int* arr, int size);
int largeNumKth(int* arr, int k, int size);

// shiftDown : 부모 노드가 자식 노드의 값을 구해 비교
void shiftDown(int* arr, int parentIdx, int size)
{
    // 최소힙
    int leftIdx = 2 * parentIdx + 1;
    int rightIdx = leftIdx + 1;
    int largeIdx = -1; // 자식 노드가 없는 경우를 방지하기 위해서
    int temp;

    if (leftIdx < size)
        largeIdx = leftIdx;

    if (rightIdx < size && arr[leftIdx] > arr[rightIdx])
        largeIdx = rightIdx;

    // largeIdx != -1 => leftIdx와 rightIdx가 모두 범위를 벗어남
    if (largeIdx != -1 && arr[largeIdx] < arr[parentIdx]) // 자식 노드 중 큰 값과 부모 노드의 값을 비교
    {
        // 값 교환
        temp = arr[largeIdx];
        arr[largeIdx] = arr[parentIdx];
        arr[parentIdx] = temp; // 값 교환

        shiftDown(arr, largeIdx, size);
    }
}

// 힙 정렬 시간 복잡도: O(N * logN)
void heapSort(int* arr, int size)
{
    // 1. 최대힙으로 만들어야 한다. => O(logN) => 원소의 개수 / 2 반복
    for (int i = size / 2 - 1; i >= 0; i--) // parentIdx의 첨자
        shiftDown(arr, i, size);

    // 2. 첫 번째 값과 마지막 값부터 교환 => O(N)
    for (int i = size - 1; i >= 1; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 0번째 원소에 힙구조에 맞지 않는 값이 들어가 있기 때문이다.
        shiftDown(arr, 0, i);
    }
}

void display(int* arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    puts("");
}

// 시간복잡도: O(NlogN), 공간 복잡도: O(N)
int largeNumKth(int* arr, int k, int size)
{
    int* copy = (int*)malloc(sizeof(int) * size); // 복사할 메모리를 할당
    memcpy(copy, arr, sizeof(int) * size);         // 메모리 복사

    heapSort(copy, size); // 복사본 배열을 정렬
    int kValue = copy[k - 1]; // k번째 값을 대입
    free(copy); // 복사본 메모리를 제거

    return kValue; // k번째 값을 리턴
}

int main()
{
    int arr[ARR_SIZE] = {6, 4, 8, 7, 5, 1, 3, 2, 10, 9};
    int k, kValue;

    printf("\n몇 번째로 큰 값을 찾으시겠습니까? ");
    scanf("%d", &k);

    kValue = largeNumKth(arr, k, 10); // 배열, k, 저장된 개수

    printf("%d번째로 큰 값은 %d입니다.\n", k, kValue);

    printf("Original Array: ");
    display(arr, 10);

    return 0;
}