01) 힙(Heap)의 개념 및 구현

들어가며

---

알고리즘 카테고리의 정렬(sorting)에 대한 포스팅을 하고 있다.
오늘은 힙 정렬(heap sorting)에 대해 포스팅 하려고 했는데
이를 위해서는 힙(heap)에 대해 먼저 공부해야 했다.

따라서 오늘은 힙(heap)에 대해 포스팅 해보고자 한다.

개념 및 특징

---

• 완전 이진 트리
• 우선순위 큐를 위해 만들짐
• 최댓값이나 최솟값을 빠르게 찾기 위해 만들어짐
• 반정렬(느슨한 정렬) 상태
• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나(혹은 작거나) 같은 이진 트리
• 중복 값을 허용

종류

---

• 최대 힙(max heap)
  부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙(min heap)
  부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

구현

---

• 보통 배열을 사용하여 구현한다.
• 구현의 편의를 위해 배열의 첫 번째 인덱스인 0은 사용하지 않는다.

소스코드(C++)

---

최대 힙(max heap)을 구현하였다.

#include <iostream>

using namespace std;

#define MAX_ELEMENT 200

struct ELEMENT{
	int key;
	int data;
public:
	ELEMENT(int _key=0, int _data=0)
		:key(_key), data(_data) {}
	friend ostream& operator << (ostream& os, const ELEMENT& e) {
		return os << "(" << e.key << "," << e.data << ")";
	}	 
};

class HEAP {
private:	
	ELEMENT heap[MAX_ELEMENT];
	size_t size;
public:
	HEAP(void):size(0) {}
	void insert(ELEMENT e) {
		heap[++size] = e;
		
		size_t ind = size;
		while(ind>1 && heap[ind/2].key < heap[ind].key) {
			ELEMENT tmp = heap[ind/2];
			heap[ind/2] = heap[ind];
			heap[ind] = tmp;
			
			ind = size/2;
		}
	}
	ELEMENT erase(void) {
		if(size == 0) {
			cout << "ERROR: NO ELEMENT IN HEAP" << endl;
			return ELEMENT(0,0);
		} 
		
		int ind = 1;
		ELEMENT res = heap[ind];
			
		heap[ind] = heap[size--];
		while(ind <= size) {
			if(heap[ind*2].key < heap[ind*2+1].key) {
				if(heap[ind*2+1].key > heap[ind].key) {
					ELEMENT e = heap[ind];
					heap[ind] = heap[ind*2+1];
					heap[ind*2+1] = e;
					
					ind = ind*2+1;
				}
				else 
					break;	
			}
			else {
				if(heap[ind*2].key > heap[ind].key) {
					ELEMENT e = heap[ind];
					heap[ind] = heap[ind*2];
					heap[ind*2] = e;
					
					ind = ind*2;
				}
				else 
					break;
			} 			
		}
		return res;
	}
	const ELEMENT& operator[](size_t i) const {
		return heap[i];
	}
	ELEMENT& operator[](size_t i) {
		return heap[i];
	} 
	friend ostream& operator << (ostream& os, const HEAP& h) {
		for(int i=1;i<=h.size;++i)
			os << h[i] << ' ';
		return os;	
	}	
};

int main(void)
{
	HEAP h;
	cout << h << endl;
	
	h.insert(ELEMENT(1,2));
	h.insert(ELEMENT(2,3));
	h.insert(ELEMENT(5,1));
	h.insert(ELEMENT(7,3));
	h.insert(ELEMENT(4,2));
	h.insert(ELEMENT(6,2));
	cout << h << endl;
	
	cout << h.erase() << endl;
	cout << h << endl;
	
	cout << h.erase() << endl;
	cout << h << endl;
	return 0;
}