[Data Structure] 힙(HEAP)이란 무엇인가? - (1)

Heap 이란 최대값 또는 최소값을 빨리 뽑아내고 싶을 때 사용하는 자료구조이며, 최대값을 우선순위로 뽑고 싶으면 MaxHeap을, 최소값은 MinHeap을 사용한다.

Heap을 사용하는 이유는 For문 탐색보다 빠르게 Min, Max 값을 탐색할 수 있기 때문이다. For문을 사용하면 Min값을 구하기 위해, 반드시 모든 값과 비교를 하며 최소값을 갱신해야하지만, Heap의 경우 O(logⁿ)의 굉장히 빠른 속도로 Min, Max 값을 구할 수 있다

#include <iostream>
using namespace std;
long long vect[10000];
int main() {

	long long n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> vect[i];
	}
	
	int min = 999;
	for (int i = 0; i < n; i++) {
		if (vect[i] < min) min = vect[i];
	}
	cout << min;
	return 0;
}

Min Heap의 경우, 값을 저장할 때는 이진트리 형태로 값을 저장하지만, 이진트리와 다른 점은 Root부분에 항상 Min값을 위치시킨다는 것이며, 저장(Push) 및 출력(Pop)이 되더라도 항상 Root부분은 Min값을 유지해야 한다. 즉, 왼쪽에는 작은 값을 저장하는 이진트리와 달리 Heap은 자식노드 값이 항상 부모 노드 값보다 크다.

< MinHeap Push 하기 >
Push는 값이 있는 바로 다음 index에 값을 삽입하게 된다.
아래 이미지에서, 4를 Push하게 되면, 부모노드와의 비교를 통해 자리를 교체(Swap)해준다.

만약에 1을 Push하게 된다면, 지금까지 배열에 저장된 값 중 가장 작은 값이므로, Root 부분에 위치시킨다.

#include <iostream>
using namespace std;
int heap[100];
int hn = 0;
void push(int value) {
	//트리의 맨 마지막 부분에 Value를 넣는다
	heap[++hn] = value;

	int now = hn;
	int parent;
	while (1) {

		parent = now / 2;
		// now가 Root이면 Swap할 것도 없다.
		if (now == 1) break;
		// MinHeap이므로, now값이 더 크면 swap할 필요없다.
		if (heap[parent] <= heap[now]) break;
		// 이 관문을 다 거쳤으면, 당연 swap!
		swap(heap[parent], heap[now]);
		now = parent; // index도 교체해준다(이제 부모가 되었으므로..)
	}
}
int main() {
	//3,5,2,4,1,6 PUSH하기!
	push(3);
	push(5);
	push(2);
	push(4);
	push(1);
	push(6);

	return 0;
}

< MinHeap Pop 하기 >
Pop하는 과정은 크게 두 가지로 나뉘는데, 하나는 return할 Min값을 백업시켜두는 것이고, 하나는 Min값이 빠진 후 다시 트리를 정렬하는 과정이다.

해당 트리에서 Min값은 1이므로, 1을 backup해두고, 가장 마지막 노드에 있는 값을 최상단으로 올려준다.
(맨 마지막 값을 올려두는 것은 굳이 다 땡겨주지 않아도 되기 때문일까 싶다)

여기서 다시, 6을 기준으로 부모노드가 더 크면 swap하는 방식으로 6의 제자리를 찾아주고, min값을 Root에 위치시켜준다.

#include <iostream>
using namespace std;
int heap[100];
int hn = 0;
void push(int value) {
	//트리의 맨 마지막 부분에 Value를 넣는다
	heap[++hn] = value;

	int now = hn;
	int parent;
	while (1) {

		parent = now / 2;
		// now가 Root이면 Swap할 것도 없다.
		if (now == 1) break;
		// MinHeap이므로, now값이 더 크면 swap할 필요없다.
		if (heap[parent] <= heap[now]) break;
		// 이 관문을 다 거쳤으면, 당연 swap!
		swap(heap[parent], heap[now]);
		now = parent; // index도 교체해준다(이제 부모가 되었으므로..)
	}
}
int pop() {
	int backup = heap[1]; // heap에 첫 번째 값은 backup!
	heap[1] = heap[hn]; // backup 해주었으니, 가장 마지막 값을 Root에 넣기
	heap[hn--] = 0; // 가장 마지막 값은 초기화해주고, 마지막 값의 index를 낮춰주기

	// 다음 min값 준비하기 과정 
	int now = 1;
	int son;
	while (1) {
		
		//일단은 첫째 자식을 선택
		son = now * 2;
		// 둘째가 존재하되, 둘째가 첫째보다 작다면 둘째 선택
		if (son + 1 <= hn && heap[son + 1] < heap[son]) son++;
		// 자식이 존재하지 않거나, 자식값이 더 크다면 break
		if (heap[now] <= heap[son] || son > hn) break;

		swap(heap[now], heap[son]);
		now = son;
	}
	return backup; // min값 출력

}
int main() {
	//3,5,2,4,1,6 PUSH하기!
	push(3);
	push(5);
	push(2);
	push(4);
	push(1);
	push(6);

	for (int i = 0; i < 6; i++) {
		cout << pop() << " ";
	}

	return 0;
}

Max Heap의 경우는 이와 반대로, 부모노드가 자식 노드보다 크게 만들어주면 된다.