C++) Heap 구현

HEAP은 최대나 최솟값을 빠르게 찾게 해주는 알고리즘.

완전 이진 트리를 기반으로 만들어진 알고리즘이다.

최대 힙과 최소 힙이 있으며 최대 힙을 구현했다.

 

1. main

int main(void) {
	fill_n(heap_arr, 100, 0); // 배열 초기화
	heap_size = 0;
	
	int node;
	
	while(node != -1) {
		cout << "Heap 현황 : ";
		for(int i = 1; i < heap_size + 1; i++) {
			cout << heap_arr[i] << " ";
		}
		cout << endl;
		 
		cin >> node;
		
		if(node <= 0) {
			break;
		}
		
		if(heap_size == 0) {
			heap_arr[1] = node;
			heap_size++;
		}
		else {
			int pp;
			cout << "1. push | 2. pop" << endl;
			cin >> pp;
			while(1) {
				if(pp == 1) {
					push(node);
					break;
				}
				else if(pp == 2) {
					pop();
					break;
				}
				else {
					cout << "1 or 2" << endl;
					cin >> pp;
				}
			}
		}
	}
}

방식은 숫자를 입력하고 난 후에 1 또는 2를 누르면 push나 pop이 되는 코드다. 단, 0 이하는 예외처리를 했다.

(pop의 경우는 아무 수나 쓰고 2를 눌러 pop을 하면 최대 값(heap의 루트값)이 pop이 된다. pop은 밑에서 더 긁적이자)

 

heap은 0으로 초기화를 했는데 값에 0이 들어가면 없는 node라고 보면 된다. heap의 최대 node 수는 99개....!!!!

 

(짜잘한 예외는 안했다.. ㅎㅎㅎㅎ node가 없을 때 pop을 하거나 뭐 그런 등등...ㅎㅎㅎㅎㅎㅎㅎ)

 

2. swap

void swap(int node, int swap_node, int swap_index) {
	heap_arr[swap_index/2] = node;
	heap_arr[swap_index] = swap_node;
}

push나 pop을 할때 노드를 바꾸기 위한 swap 함수.

 

3. push

void push(int node) {
	heap_size += 1;
	int index = heap_size;
	while(index != 1 && heap_arr[index/2] < node) {
		swap(node, heap_arr[index/2], index);
		index /= 2;
	}
	if(index == 1) {
		return;
	}
	else {
		heap_arr[index] = node;
	}
}

입력 받은 값(node)를 push 한다. 생각보다 간단했다. 

1. push 하고자 하는 값(이하 node)을 배열 끝에 넣는다.

2. 부모 노드와 node를 비교하면서 node가 더 클경우 부모 node와 swap한다.

3. 2가 끝날때 까지 반복

 

4. pop

void pop() {
	//힙의 삭제는 가장 큰 값인 루트를 삭제하는 것. 
	//마지막 node와 뺄 node 바 꿈
	int temp = heap_arr[1]; 
	heap_arr[1] = heap_arr[heap_size];
	heap_arr[heap_size] = 0;
	 
	int index = 1;
	while(index < heap_size && heap_arr[index * 2] != 0) {
		if(heap_arr[index] > heap_arr[index*2] && heap_arr[index] > heap_arr[index*2 +1]) {
			break;
		}
		if(heap_arr[index*2] > heap_arr[index*2+1]) {
			swap(heap_arr[index*2], heap_arr[index], index * 2);
			index *= 2;
		}
		else {
			swap(heap_arr[index*2 + 1], heap_arr[index], index * 2 + 1);
			index = index * 2 + 1;
		}
	}
	heap_arr[heap_size] = 0;
	heap_size--;
}

pop은 좀 헷갈렸다. 

Heap에서의 pop은 루트노드 즉, 가장 큰 값을 삭제하는 것이다.

 

1. 루트 노드와 마지막 노드의 자리를 바꾼다.

2. 자식 노드 2개 중 더 큰 값과 비교를 하는데 부모 노드가 자식 노드보다 더 클 경우가 나올때 까지 한다.

 - 큰 값과 비교를 하는 이유는 Heap은 부모 노드가 자식 노드보다 더 커야하기 때문이다.

3. heap의 마지막 노드를 0으로 바꿔 지워주면서 heap의 크기를 하나 줄인다.

---

#include <bits/stdc++.h>

using namespace std;

int heap_arr[100];
int heap_size;

void swap(int node, int swap_node, int swap_index) {
	heap_arr[swap_index/2] = node;
	heap_arr[swap_index] = swap_node;
}

void push(int node) {
	heap_size += 1;
	int index = heap_size;
	while(index != 1 && heap_arr[index/2] < node) {
		swap(node, heap_arr[index/2], index);
		index /= 2;
	}
	if(index == 1) {
		return;
	}
	else {
		heap_arr[index] = node;
	}
} 

void pop() {
	//힙의 삭제는 가장 큰 값인 루트를 삭제하는 것. 
	//마지막 node와 뺄 node 바 꿈
	int temp = heap_arr[1]; 
	heap_arr[1] = heap_arr[heap_size];
	heap_arr[heap_size] = 0;
	 
	int index = 1;
	while(index < heap_size && heap_arr[index * 2] != 0) {
		if(heap_arr[index] > heap_arr[index*2] && heap_arr[index] > heap_arr[index*2 +1]) {
			break;
		}
		if(heap_arr[index*2] > heap_arr[index*2+1]) {
			swap(heap_arr[index*2], heap_arr[index], index * 2);
			index *= 2;
		}
		else {
			swap(heap_arr[index*2 + 1], heap_arr[index], index * 2 + 1);
			index = index * 2 + 1;
		}
	}
	heap_arr[heap_size] = 0;
	heap_size--;
}

int main(void) {
	fill_n(heap_arr, 100, 0); // 배열 초기화
	heap_size = 0;
	
	int node;
	
	while(node != -1) {
		cout << "Heap 현황 : ";
		for(int i = 1; i < heap_size + 1; i++) {
			cout << heap_arr[i] << " ";
		}
		cout << endl;
		 
		cin >> node;
		
		if(node <= 0) {
			break;
		}
		
		if(heap_size == 0) {
			heap_arr[1] = node;
			heap_size++;
		}
		else {
			int pp;
			cout << "1. push | 2. pop" << endl;
			cin >> pp;
			while(1) {
				if(pp == 1) {
					push(node);
					break;
				}
				else if(pp == 2) {
					pop();
					break;
				}
				else {
					cout << "1 or 2" << endl;
					cin >> pp;
				}
			}
		}
	}
}

생각보다 헷갈리긴 해서 그려가면서 코딩했다.