[자료구조] C로 Heap 만들기

Heap?

힙은 최대/최소 값을 빠르게 찾기 위해 고안된 완전 이진 트리입니다. 부모 노드가 자식 노드보다 항상 크거나(Max Heap) 작게(Min Heap) 만들어 루트 노드가 원하는 값이 되도록 만듭니다.
힙은 우선순위 큐, 힙정렬과 같이 다양한 곳에서 사용되는 자료구조 입니다.

힙 특징

1. 힙은 반드시 완전이진트리 입니다.
2. 최대힙은 부모 >= 자식, 최소힙은 부모 <= 자식이 언제든지 성립합니다. 단, 형제 노드끼리는 대소비교를 하지 않습니다.

힙 종류

최대 힙 (Max Heap)

최대 힙은 루트에 가장 큰 값이 위치하는 힙 입니다. 부모 >= 자식이 항상 성립합니다.

최소 힙 (Min Heap)

최소 힙은 루트에 가장 작은 값이 위치하는 힙 입니다. 부모 <= 자식이 항상 성립합니다.

동작 원리

Max Heap 기준으로 C로 구현한 예제와 함께 설명하겠습니다.

구조체 선언

typedef struct {
    int items[MAX_SIZE];
    int size;
} MaxHeap;

완전 이진 트리인 힙 구현에는 배열을 주로 사용합니다. 완전 이진 트리는 루트에서 리프로, 왼쪽에서 오른쪽으로 데이터를 추가하기 때문에, 메모리 낭비 없이 인덱스 계산만으로 부모-자식을 찾을 수 있습니다.

삽입

void insert(MaxHeap* h, int value) {
    if (h->size >= MAX_SIZE) return;

    int index = h->size;
    h->items[index] = value;
    h->size++;

    while (index > 0 && h->items[index] > h->items[(index - 1) / 2]) {
        int parentIndex = (index - 1) / 2;
        swap(&h->items[index], &h->items[parentIndex]);
        index = parentIndex;
    }
}

힙에 새 값을 추가할때는 일단 현재 힙의 마지악에 추가합니다. 그 다음, 부모 노드와 비교해가며 힙의 성질을 만족 할 때 까지 swap하며 추가한 값이 맞는 위치에 있게 합니다.

삭제

int delete(MaxHeap* h) {
    if (h->size == 0) return -1;
    int rootValue = h->items[0];

    h->items[0] = h->items[h->size - 1];
    h->size--;
    
    int index = 0;
    while (1) {
        int largest = index;
        int leftChild = index * 2 + 1;
        int rightChild = index * 2 + 2;

        if (leftChild < h->size && h->items[leftChild] > h->items[largest]) {
            largest = leftChild;
        }
        if (rightChild < h->size && h->items[rightChild] > h->items[largest]) {
            largest = rightChild;
        }

        if (largest == index) break;

        swap(&h->items[largest], &h->items[index]);
        index = largest;
    }

    return rootValue;
}

힙에서 삭제는 보통 최대/최소값이 있는 루트노드가 삭제됩니다. 삭제 후 빈 루트노드에 제일 끝에 있는 값을 옮긴 후, 자식 노드와 비교하며 힙의 성질을 만족할 때 까지 swap합니다. 힙이 업데이트 되었다면 맨 끝 노드는 삭제해서 힙을 재구성 합니다.

전체 코드

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int size;
} MaxHeap;


void swap(int* a, int*b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void insert(MaxHeap* h, int value) {
    if (h->size >= MAX_SIZE) return;

    int index = h->size;
    h->items[index] = value;
    h->size++;

    while (index > 0 && h->items[index] > h->items[(index - 1) / 2]) {
        int parentIndex = (index - 1) / 2;
        swap(&h->items[index], &h->items[parentIndex]);
        index = parentIndex;
    }
}

int delete(MaxHeap* h) {
    if (h->size == 0) return -1;
    int rootValue = h->items[0];

    h->items[0] = h->items[h->size - 1];
    h->size--;
    
    int index = 0;
    while (1) {
        int largest = index;
        int leftChild = index * 2 + 1;
        int rightChild = index * 2 + 2;

        if (leftChild < h->size && h->items[leftChild] > h->items[largest]) {
            largest = leftChild;
        }
        if (rightChild < h->size && h->items[rightChild] > h->items[largest]) {
            largest = rightChild;
        }

        if (largest == index) break;

        swap(&h->items[largest], &h->items[index]);
        index = largest;
    }

    return rootValue;
}


void printHeap(MaxHeap* h) {
    printf("Heap: ");
    for (int i = 0; i < h->size; i++) {
        printf("%d ", h->items[i]);
    }
    printf("\n");
}


int main() {
    MaxHeap heap;
    heap.size = 0;

    insert(&heap, 10);
    insert(&heap, 50);
    insert(&heap, 30);
    insert(&heap, 20);
    insert(&heap, 60);
    printHeap(&heap);

    int deleted = delete(&heap);
    printf("deleted: %d\n", deleted);
    printHeap(&heap);

    deleted = delete(&heap);
    printf("deleted 값: %d\n", deleted);
    printHeap(&heap);

    return 0;
}