[자료구조] 힙(Heap)이란?

힙이란?

• 완전이진트리의 일종이다.
• 힙은 중복된 값을 허용한다.
• 여러 값들 중 최대값 혹은 최소값을 빠르게 찾아내기 위한 자료구조이다.
• Max heap은 가장 큰 값을 빠르게 찾기 위한 것이고 Min Heap은 가장 작은 값을 빠르게 찾기 위한 것이다.

최대힙

max heap

• Max Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.
• 부모노드의 key ≥ 자식 노드의 key

최소힙

Min Heap

 

• Min Heap 은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.
• 부모노드의 key ≤ 자식 노드의 key

 

힙 구현

Heap은 배열을 통해 쉽게 구현할 수 있다. 이진 탐색 트리의 경우에는 연결리스트로 구현하였는데

Heap은 배열로 구현하는 이유가 무엇일까? 그 이유는 Heap이 완전 이진 트리이기 때문이다. 완전 이진트리의 특성상

왼쪽부터 오른쪽으로 차곡차곡 노드가 저장되므로 배열의 구조를 사용할 수 있게 된다.

 

Max Heap의 구조

위 그림은 Max Heap을 배열로 표현한 것이다. 여기서 특이한 점은 0번 index를 사용하지 않는다는 것인데

이는 구현을 쉽게 하기 위해서이다. index를 통해 노드에 접근할 수 있는데, 다음과 같다.

 

부모노드의 index = 자식노드의 index ÷ 2

왼쪽 자식 노드의 index = 부모노드의 index × 2

오른쪽 자식 노드의 index = 부모노드의 index × 2 + 1

 

---

힙 삽입

1. 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. ( 배열의 마지막에 원소를 추가한다.)
2. 새로운 노드를 부모 노드와 비교해서 교환해야 한다면 힙의 성질을 만족할 때 까지 교환한다.

예를 들어 위의 Max Heap에 새로운 노드(key=8)를 추가한다고 하자. 

max heap 삽입

첫 번째로 배열의 가장 마지막 위치에 새로운 원소 8을 추가합니다.

max heap 삽입

두 번째로 부모노드인 index 4번 노드와 키 값을 비교한다. 이 때 자식 노드인 index 8번 노드가 키값이 더 크므로 (8>4) 부모노드와 위치를 교환한다.

max heap 삽입

마지막으로 부모노드인 index 2번 노드와 키 값을 비교한다. 이 때 자식 노드인 index 4번 노드가 키 값이 더 크므로 (8>7) 부모노드와 위치를 교환한다. 이렇게 하면 Max Heap의 성질을 만족하게 되고 삽입과정이 종료된다.

 

Max Heap을 예로 들었지만, Min Heap은 반대로 부모노드가 자식 노드보다 작도록 교환하면 된다.

void max_heap_insert(Heap* h, element item) {
	int i;
	i = ++(h->size); //마지막 위치(마지막 원소의 index+1)

	// 루트 노드가 아니고, 사빙할 값이 적절한 위치를 찾을 때까지
	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2]; //자식 노드와 부모 노드 교환
		i /= 2; //한 레벨 상승
	}

	h->heap[i] = item;
}

---

힙 삭제

Heap에서의 삭제는 루트 노드를 삭제하고 반환한다는 뜻이다.

• Max Heap에서의 삭제는 가장 큰 키 값을 가진 루트 노드를 삭제하고 반환한다는 뜻이다.
• Min Heap에서의 삭제는 가장 작은 키 값을 가진 루트 노드를 삭제하고 반환한다는 뜻이다.

1. 루트노드를 삭제한다 ( 나중에 값을 반환해야하므로 따로 저장한다)
2. 삭제된 루트 노드의 위치에 힙의 가장 마지막 노드를 가져온다.
3. 힙의 조건에 맞게 위치를 재설정한다. (이것을 heapify 라고 한다.)

max heap 삭제

1. 루트 노드를 삭제한다( 나중에 값을 반환해야 하므로 따로 저장해놓는다.)

2. 삭제된 루트 노드의 위치에 힙의 가장 마지막 노드를 가져온다.

max heap 삭제

3. 힙의 조건에 맞게 위치를 재설정한다. (Heapify)

 

이때 주의할 점은 비교할 노드보다 큰 자식 노드가 2개 있을 때, 더 큰 값을 가진 자식 노드와 교환해야한다는 것이다.

마찬가지로 힙의 조건에 맞게 위치를 재설정하면 된다.

element max_heap_delete(Heap* h) {
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->size)--];
	parent = 1;
	child = 2;

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

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

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}

	h->heap[parent] = temp;

	return item;
}

 

전체 코드

#include <stdio.h>
#define MAX_SIZE 100

typedef struct { // 힙의 노드
	int key; //힙의 key
}element;

typedef struct { //힙 자료구조
	element heap[MAX_SIZE];
	int size;
}Heap;

void max_heap_insert(Heap* h, element item) {
	int i;
	i = ++(h->size); //마지막 위치(마지막 원소의 index+1)

	// 루트 노드가 아니고, 사빙할 값이 적절한 위치를 찾을 때까지
	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2]; //자식 노드와 부모 노드 교환
		i /= 2; //한 레벨 상승
	}

	h->heap[i] = item;
}

element max_heap_delete(Heap* h) {
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->size)--];
	parent = 1;
	child = 2;

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

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

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}

	h->heap[parent] = temp;

	return item;
}

int main() {
	Heap max_heap;
	element item;
	item.key = 9;
	max_heap_insert(&max_heap, item);
	item.key = 7;
	max_heap_insert(&max_heap, item);
	item.key = 6;
	max_heap_insert(&max_heap, item);
	item.key = 4;
	max_heap_insert(&max_heap, item);
	item.key = 5;
	max_heap_insert(&max_heap, item);
	item.key = 1;
	max_heap_insert(&max_heap, item);
	item.key = 3;
	max_heap_insert(&max_heap, item);
	item.key = 8;
	max_heap_insert(&max_heap, item);

	while (max_heap.size > 0) {
		item = max_heap_delete(&max_heap);
		printf("%d ", item.key);
	}

	return 0;
}