[Heap] C언어로 Max Heap 구현하기
HEAP이란?
Complete Binary Tree에 해당하는 자료구조로, Max Heap과 Min Heap이 있다.
Complete Binary Tree라는 것은, Tree의 각 레벨 노드들이 왼쪽에서 오른쪽으로 채워지는 Binary Tree를 의미한다. 만약 아래의 왼쪽 그림에서 45 노드가 62의 왼쪽 자식이 아닌 오른쪽 자식 노드이거나, 24 노드가 존재하지 않았다면 왼쪽 그림을 Complete 하다고 볼 수 없을 것이다. 하지만 현재 왼쪽 그림은 level 0과 level1은 모든 자리가 채워져 있고, level2의 경우 왼쪽부터 채워져 있기 때문에 Complete Binary Tree라고 볼 수 있다.
Max Heap은 모든 부모노드가 자식노드들보다 큰 경우이고, Min Heap은 모든 부모노드가 자식노드들보다 작은 경우이다. 아래 그림을 보면, 왼쪽은 Max Heap이고 오른쪽은 그렇지 않다. 왜냐하면 왼쪽은 모든 부모노드가 본인의 자식노드보다 크지만, 오른쪽의 경우 부모노드인 6이 자식노드인 7보다 작기 때문이다. 따라서 Max 힙의 경우 root node가 최댓값이고, Min 힙의 경우 root node가 최솟값이다.
1. Heap을 array에 저장하기
Heap은 보통 array에 저장된다. 아래 그림과 같이 그래프로 표현된 힙이 1:1 mapping 관계를 가진 array에 저장하는 것이다. array index가 1부터 시작한다고 가정했을 때, left child의 index는 (2 * i)가 되고, right child의 index는 (2 * i + 1)이 된다. parent는 floor(i / 2)가 된다.
2. Heapify
Heap의 경우 insert, delete 등의 기능을 수행할 수 있어야 하는데, 이 때도 Heap Property를 유지해야 한다. 그래서 이용하는 것이 Heapify이다. insert를 할 때는 끝에 새로운 요소를 넣고 부모노드와 비교해나가는 방식을 주로 사용하지만, 처음 Heap을 build 할 때나 delete를 할 때는 Heapify를 한다. Heapify는 자식 노드 중 더 큰 값과 현재 부모노드를 비교하여, 자식노드가 더 크다면 둘을 switch 하는 과정을 반복하는 일이다. 자세한 것은 이후 구현될 코드에서 볼 수 있다.
MAX HEAP을 C언어로 구현하기
1. Header File
Max Heap의 기본이 될 MaxHeap 구조체를 선언한다. capacity는 element의 최대 개수, count는 현재 element의 개수, elements에는 element 들의 max heap의 property에 맞게 순서대로 array 형태로 저장된다.
나머지 함수들은 아래서 자세히 설명한다.
// main.h
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX_CAPACITY 100
typedef struct MAXHEAP {
int capacity;
int count;
int *elements;
} MaxHeap;
// basic_func.c
int findParent(int child);
void swap(MaxHeap **heap, int idx1, int idx2);
int findLeftChild(int par);
int findRightChild(int par);
// main_func.c
bool Insert(MaxHeap **heap, int a);
bool Delete(MaxHeap **heap);
int Max(MaxHeap *heap);2. Main Function
입력에 따른 동작은 아래와 같다. output은 각 동작 수행 후 array내 모든 요소를 순서대로 출력하는 것이다. (File IO로 이뤄지므로, input 파일에 명령 입력이 있고, 그에 따른 output을 output 파일에 저장하면 된다.)
I (int value) : insert given int value
D (int value) : delete given int value
M : get maximum (이 경우만 특별히 output으로 maximum 값 하나만 출력한다.)
// main.c
#include "main.h"
int main(int args, char **argv) {
if (args != 3) {
printf("Corrct Usage : [program] [input file] [output file]\n");
return 1;
}
FILE *inFile = fopen(argv[1], "r");
FILE *outFile = fopen(argv[2], "w");
char c;
MaxHeap *heap = (MaxHeap *)malloc(sizeof(MaxHeap));
heap->capacity = MAX_CAPACITY;
heap->count = 0;
heap->elements = (int *)malloc(sizeof(int) * heap->capacity);
while ((c = fgetc(inFile)) != EOF) {
if (!isalpha(c)) continue;
if (c == 'I') {
int a;
fscanf(inFile, "%d", &a);
if (Insert(&heap, a)) {
fputc('I', outFile);
for (int i = 0; i < heap->count; i++) fprintf(outFile, " %d", heap->elements[i]);
} else {
printf("[Error] Insertion Failed\n");
return 1;
}
} else if (c == 'D') {
if (Delete(&heap)) {
fputc('D', outFile);
for (int i = 0; i < heap->count; i++) fprintf(outFile, " %d", heap->elements[i]);
} else {
printf("[Error] Deletion Failed\n");
return 1;
}
}
else if (c == 'M') {
int max = Max(heap);
if (max) fprintf(outFile, "M %d", max);
else {
printf("[Error] Max Find Failed\n");
return 1;
}
}
else fputs("[Error] NO FUNCTION\n", outFile);
fputc('\n', outFile);
}
}3. Heap의 기본적인 함수들
아래 코드는 heap에서 기본적으로 갖춰야 할 간단한 함수들을 구현한 것이다. 앞서 array 형태로 heap을 저장해야 한다는 것을 이야기할 때 서술했듯, parent는 자식노드에서 2를 나누면 되고, left child는 부모노드에서 2를 곱하면 되고, right child는 2를 곱하고 1을 더해주어야 한다. 다만, 해당 설명은 index가 1에서 시작했을 때 기준이므로, index가 0부터 시작하는 c언어에서는 그에 맞게 조금 달리 작성해주어야 하다. 아래 코드를 보면 쉽게 이해가 가능하다.
swap의 경우 node를 insert 해준 후 제자리를 찾아가게 하거나, heapify를 할 때 아주 많이 사용되므로, 기본 기능에 넣어둔다.
// basic_func.c
#include "main.h"
int findParent(int child) {
return (child - 1) / 2;
}
void swap(MaxHeap **heap, int idx1, int idx2) {
int temp = (*heap)->elements[idx1];
(*heap)->elements[idx1] = (*heap)->elements[idx2];
(*heap)->elements[idx2] = temp;
}
int findLeftChild(int par) {
return par * 2 + 1;
}
int findRightChild(int par) {
return par * 2 + 2;
}4. Insert, Delete, Max 구현
마지막으로 해당 구현에서 가장 중요한 부분인 Insert, Delete, Max를 구현하는 부분이다. heapify의 경우 delete에서만 사용하기 때문에 따로 함수를 만들지 않고 delete 안에 녹여냈다.
우선 Insert()의 경우, array의 마지막 요소로 새로운 element를 추가해주는 것으로 시작한다. 그리고 부모 element가 추가하고자 하는 element보다 클 경우 둘을 switch 하는 것을 반복한다.
delete()는 max값, 즉 root 값을 delete 해주는 것을 의미한다. 이를 바탕으로 delete를 구현했을 때, 우선 삭제하고자 하는 root element와 array 내 가장 마지막 element를 switch 하고 count를 하나 줄여주는 것으로 시작한다. 이로서 maximum 값을 삭제하는 것은 완료된 것이다. 그러고 나서, 이제는 앞서 언급했던 대로 heapify를 해줘야 한다. heapify는 현재 element의 자식 element가 더 클 때까지 반복한다. 만약 left child가 더 크다면 현재 element와 left child를 switch 해주고, right child가 더 크다면 right child와 switch 해주면 된다.
마지막으로 Max()는 단순히 array 내 가장 첫번째 element를 리턴해주면 된다.
// main_func.c
#include "main.h"
bool Insert(MaxHeap **heap, int a) {
if ((*heap)->count >= (*heap)->capacity) return false;
if ((*heap)->count == 0) {
(*heap)->elements[0] = a;
(*heap)->count += 1;
return true;
}
int curidx = (*heap)->count;
int paridx = findParent(curidx);
(*heap)->elements[curidx] = a;
while ((*heap)->elements[curidx] > (*heap)->elements[paridx]) {
swap(heap, curidx, paridx);
curidx = paridx;
paridx = findParent(curidx);
}
(*heap)->count += 1;
return true;
}
bool Delete(MaxHeap **heap) {
if ((*heap)->count == 0) return false;
swap(heap, 0, (*heap)->count - 1);
int curidx = 0;
int left = 1;
int right = 2;
while (((*heap)->elements[curidx] < (*heap)->elements[left])
|| ((*heap)->elements[curidx] < (*heap)->elements[right])) {
int bigger = (((*heap)->elements[left] > (*heap)->elements[right])) ? left : right;
if (bigger >= (*heap)->count) break;
swap(heap, curidx, bigger);
curidx = bigger;
left = findLeftChild(curidx);
right = findRightChild(curidx);
}
(*heap)->count -= 1;
return true;
}
int Max(MaxHeap *heap) {
if (heap->count == 0) return NULL;
else return heap->elements[0];
}