[자료구조] 힙 (Heap)

 

힙 (Heap)

힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조입니다.

 

힙의 종류

힙에는 두 가지 종류의 힙 트리가 존재합니다. 하나는 부모 노드의 키 값이 자식 노드보다 큰 최대 힙 (Max Heap), 다른 하나는 부모 노드의 키 값이 자식 노드보다 작은 최소 힙(Min heap)입니다.

루트 노드가 최대면 최대 힙이고 최소면 최소 힙임을 알 수 있습니다.

최대 힙. 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리.

최소 힙. 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리.

 

힙 구현

최대 힙의 함수들을 각각 구현해보면서 최대 힙 트리가 어떻게 동작하는지 차근차근 알아가보겠습니다.

 

insert_max_heap(*h, item)

최대 힙의 삽입 연산은 다음과 같이 동작합니다.

1. 힙 크기를 하나 증가시킨다.
2. 트리를 거슬러 올라가면서 부모 노드와 비교해서 부모 노드보다 크다면 인덱스를 2로 나눠 조건이 맞지 않을 때까지 계산한다.
3. 새로 만든 노드를 적절히 계산된 위치에 삽입한다.

코드로 나타내면 아래와 같습니다.

void insert_max_heap(Heap *h, element item) {
	int i = ++(h->heap_size); // 1.

	while((i != 1) && (item.key > h->heap[i / 2].key)) { // 2.
		h->heap[i] = h->heap[i/2];
		i /= 2;
	}
	h->heap[i] = item; // 3.
}

 

delete_max_heap(*h)

최대 힙의 삭제 연산은 다음과 같이 동작합니다. 이 때, 삭제하는 노드는 루트 노드입니다. 루트 노드를 삭제하면 트리를 필연적으로 재구성해야 합니다. 따라서 힙 트리에서 노드를 삭제했다면 부가적인 연산이 필요합니다.

재구성은 일단 가장 끝의 원소를 루트로 올리고, 값이 작은 자식이 나올 때까지 원소를 밑으로 내리면 됩니다.

1. 루트 노드 값을 return하기 위해 item 변수로 옮긴다.
2. 가장 끝에 있는 노드를 일단 temp 변수에 대입해준다. 또한 힙의 크기를 1 줄인다.
3. child가 h의 heap_size보다 작을동안 반복문을 수행한다. 힙의 크기를 넘어서 원소가 접근하면 안 되기 때문이다.
4. 만약 child가 h의 heap_size보다 작고 왼쪽 자식 노드의 키가 오른쪽 자식 노드의 키보다 작다면 child를 1 올린다. 그래서 한 단계 아래로 이동할 때 오른쪽으로 원소가 이동할 수 있도록 한다.
5. 부모 노드의 키가 자식 노드의 키보다 크다면 최대 힙 트리의 정의에 부합하므로 더 이상 수행하지 않아도 된다.
6. 그렇지 않으면 부모 노드와 자식 노드간의 위치를 변경해 한 단계 아래로 이동한다.
7. 루트 노드로 올릴 노드 temp 변수에 저장했었다(2번 참고). 이를 루트 인덱스에 넣어준다.

코드로 나타내면 아래와 같습니다.

element delete_max_heap(Heap *h) {
	int parent = 1, child = 2;
	element item, temp;
	item = h->heap[1]; // 1.
	temp = h->heap[(h->heap_size)—]; // 2.

	while(child <= h->heap_size) { // 3.
		if((child < h->heap_size) && (h->heap[child].key < h->heap[child + 1].key)) { // 4.
			child++;
		}

		if(temp.key >= h->heap[child].key) break; // 5.

		h->heap[parent] = h->heap[child]; // 6.
		parent = child; // 6.
		child *= 2; // 6.
	}
	h->heap[parent] = temp; // 7.
	return item;
}

 

힙 정렬

힙 정렬은 힙 트리를 이용해 정렬을 하는 것을 말합니다. 사실 최대 힙과 최소 힙은 각각 루트에 최댓값과 최솟값이 이미 있습니다. 루트를 계속 꺼내면 힙의 정의에 의해 그 다음 큰 값(혹은 작은 값)이 계속 루트에 상주하게 됩니다. 따라서 트리에 노드가 없을 때까지 힙 트리의 삭제 함수를 계속 호출만 하면 됩니다.

void heap_sort(element a[], int n) {
	Heap *h;
	h = create();
	init(h);

	for(int i = 0; i < n; i++) {
		insert_max_heap(h, a[i]);
	}

	for(int i = n - 1; i >= 0; i—) {
		a[i] = delete_max_heap(h);
	}

	free(h);
}