'최소힙'에 해당되는 글 1건

힙(Heap) 개념

힙이라는 자료구조는 무엇일까요? 

힙은 일종의 트리로 수의 집합에서 가장 작은 수(키)나 가장 큰 수만을 자주 꺼내올때 유용한 자료구조입니다. 

우리는 어떤 정수형 배열이 있다고 가정해볼게요.

이 배열에서 가장 작은 원소를 구하려면 어떻게 해야할까요? 우선 for루프를 돌겠죠? 배열 하나하나마다 비교해서 가장 작은 값을 찾아오면 시간복잡도는 O(n)이 될겁니다. 

하지만 우리의 힙은 이 작업은 logn의 속도로 해준답니다. 

어떻게 이것이 가능할까요?

힙은 트리를 쓴다고 했죠? 이 트리는 평범한 트리는 아니고 완전 이진 트리라는 트리인데요. 항상 자식은 두개밖에 없고, leaf의 가장 왼쪽부터 채우게 됩니다.

그림에서 왼쪽은 완전 이진 트리인데, 오른쪽은 완전 이진 트리가 아니군요. 왼쪽 트리는 잎 노드의 왼쪽부터 전부 채워져있는 형태인데, 오른쪽 트리는 그렇지 않으니까요.

힙은 크게 두가지가 있습니다. 최소힙과 최대힙이 그것들인데요. 

최소힙은 가장 작은 값이 루트이고, 최대힙은 가장 큰 값이 루트입니다. 

우리는 그 중에서도 가장 작은 것이 루트인 최소힙을 구현해보도록 할게요. 어차피 최대힙의 구현도 거의 똑같거든요. 

최소힙

그림을 보면서 최소힙을 이해하도록 합시다. 

규칙을 알았다면 이제 본격적으로 구현해볼까요? 우선 heap이라는 구조체부터 정의해볼까요?

typedef struct heap {
	int arr[MAX_N];
	int size;
} heap;

아까 말한대로 heap을 배열의 형태로 구현할 것이기 때문에 arr이라는 배열이 구조체에 선언되어 있죠. 그리고 heap의 사이즈 역시 선언되어있습니다.

1. insert

이제 heap의 삽입과정을 보도록 합시다. 어떤 수가 추가되려면 일단 잎노드부터 계속 비교하여 자리를 찾아야되는데요, 우리는 최소힙을 구현하니까 지금 삽입될 노드가 트리의 노드보다 크면 멈춰야합니다. 하지만 루트까지 비교했는데 자신보다 작은 노드를 찾을 수 없다면 자신이 가장 작은 값이라는 것이니 루트가 되겠죠? 

아래 그림은 트리에서 1이 삽입되는 과정을 보여줍니다.

우선 맨 아래의 한자리, 즉 here가 현재 삽입될 삽입될 자리를 의미합니다. here의 인덱스는 8이 되겠네요. 8의 부모인덱스는 8/2=4 입니다. 그러니까 5와 1을 비교합니다. 1이 더 작네요. 그렇다면 5는 here의 자리로 오게됩니다.

이제 here자리는 인덱스 4가 되었습니다. 부모 인덱스는 2로써 4라는 값을 갖고 있네요. 4와 1을 비교합니다. 1이 더 작네요. 그러면 here의 자리는 부모인덱스 자리인 2가 됩니다.

부모 인덱스는 1이 됩니다. 그 값은 2로 현재 추가될 1보다 크네요. here는 1의 인덱스 위치로 옮겨집니다. 

이제 부모는 없습니다. 그러므로 here의 자리에 1이 삽입되는 것이죠.

이 상황을 구현한 코드가 아래에 있습니다. 

void insert(heap* hp,int data) {
	int here = ++hp->size;
	
	while ((here!=1)&&(data<hp->arr[here/2])) {
		hp->arr[here] = hp->arr[here / 2];
		here /= 2;
	}
	hp->arr[here] = data;
}

의외로 코드가 길지 않죠?? 

hp는 heap 구조체 포인터를 의미하는 것이고 data는 현재 추가될 데이터를 말합니다. 그래서 data는 트리의 노드 값과 비교하여 data가 더 작다면 계속 올라갑니다.

언제까지요? 자신보다 작은 트리의 노드를 만날때까지요.

하지만 더이상 트리에서 data보다 작은 값을 만날 수 없다면 here는 1이 되므로 루트자리가 됩니다.

2. deleteData

이제 heap에서 꺼내오는 함수를 구현해보도록 하죠. 우선 root 위치에 있는 값을 꺼냅니다. 그 후 가장 끝에 있는 노드를 root 위치에 다시 붙이죠. 그리고 나서 계속 자식들과 비교하여 위치를 찾습니다. 

위의 heap에서 1을 꺼내오는 과정을 아래에서 보여주고 있습니다. 

1을 우선 꺼냅니다. 1은 나가있어 뒤지기 시르면 

루트가 비어있네요. 루트를 가장 끝에 있는 노드 5로 매꿉니다.

이제 5라는 노드의 자식을 비교해서 위치를 찾는데요. 두 자식보다 자신이 더 작다면 멈추면 됩니다. 두 자식보다 가장 작은 녀석은 2인데, 2가 5보다 작으므로 5와 2의 위치를 바꿔줍니다. 

그러면 아래와 같은 트리가 되겠죠?

5의 자식은 4와 7이 되었습니다. 둘 중 가장 작은 자식은 4인데, 5는 4보다 크지요? 그러니까 4와 5의 위치를 바꿔줍니다. 

이제 더 이상 내려갈 곳이 없군요. 5의 위치는 이제 정해졌습니다.

자 보세요. 1을 꺼냈어도 완전 이진트리의 모양을 유지하고 있고 가장 작은 값이 루트인것이 보이죠? 이제 코드로 구현하면 됩니다.

int deleteData(heap *hp) {
	if (hp->size == 0) return -1;
	int ret = hp->arr[1];
	hp->arr[1]=hp->arr[hp->size--];
	int parent = 1;
	int child;

	while (1) {
		child = parent * 2;
		if (child + 1 <= hp->size && hp->arr[child]>hp->arr[child + 1])
			child++;

		if (child>hp->size||hp->arr[child] > hp->arr[parent]) break;
		
		swap(&hp->arr[parent], &hp->arr[child]);
		parent = child;
	}
	
	return ret;
	
}

int ret = hp->arr[1];
	hp->arr[1]=hp->arr[hp->size--];

이후 while루프 안에서 가장 작은 자식과 자신을 비교해서 자신이 더 작을때까지 돌거나 더 이상 자식이 없을 때까지 돕니다.

전체 코드

이제 전체코드를 통해서 직접 실행해 보세요.

#include <stdio.h>
#define MAX_N 1024
typedef struct heap {
	int arr[MAX_N];
	int size;
} heap;

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void initHeap(heap *hp) {
	hp->size = 0;
}
void insert(heap* hp,int data) {
	int here = ++hp->size;
	
	while ((here!=1)&&(data<hp->arr[here/2])) {
		hp->arr[here] = hp->arr[here / 2];
		here /= 2;
	}
	hp->arr[here] = data;
}

int deleteData(heap *hp) {
	if (hp->size == 0) return -1;
	int ret = hp->arr[1];
	hp->arr[1]=hp->arr[hp->size--];
	int parent = 1;
	int child;

	while (1) {
		child = parent * 2;
		if (child + 1 <= hp->size && hp->arr[child]>hp->arr[child + 1])
			child++;

		if (child>hp->size||hp->arr[child] > hp->arr[parent]) break;
		
		swap(&hp->arr[parent], &hp->arr[child]);
		parent = child;
	}
	
	return ret;
	
}
int main() {
	heap hp;
	initHeap(&hp);
	
	insert(&hp, 3);
	insert(&hp, 5);
	insert(&hp, 1);
	insert(&hp, 2);
	insert(&hp, 8);
	
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));

	printf("\n");
	insert(&hp, 9);
	insert(&hp, 3);
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));

	printf("\n");
	insert(&hp, 1);
	insert(&hp, 9);
	insert(&hp, 10);
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));
	printf("%d\n", deleteData(&hp));

}