힙 트리 이론

이진트리란 ?

각 노드가 최대 두개의 자식 노드를 가지는 트리

 

이진 검색 트리 특징

1. 왼쪽을 타고 가면 현재 값보다 작다
2. 오른쪽을 타고 가면 현재 값보다 크다

이진 검색 트리 문제

1. 그냥 무식하게 추가하면, 한쪽으로 기울어져서 균형이 깨진다
2. 트리 재배치를 통해 균형을 유지하는것이 과제(AVL, Red-Black)

 

힙 트리 특징

1. [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다
2. 이진트리에 비해 조건이 까다롭지 않다
3. 노드 개수를 알면 트리 구조는 무조건 확정할 수 있다.

힙 트리 구조

1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있다(완전 이진 트리)
2. 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야한다.

배열을 이용해서 힙 구조를 바로 표현할 수 있다.

1. i번 노드의 왼쪽자식은[(2*i)+1] 번
2. i번 노드의 오른쪽자식은[(2*i)+2] 번
3. i번 노드의 부모는[(i-1)/2] 번

새로운 값 추가

1. 우선 트리 구조부터 맞춰준다
2. 도장깨기를 시작한다(부모노드랑 비교해서 크다면 올려보냄)

최대값 꺼내기

1. 힙트리 특성상 최대값은 무조건 루트 노드에 있는 값이다
2. 최대값을 먼저 제거 한다
3. 제일 마지막에 위치한 데이터를 루트로 옮긴다
4. 역 도장깨기를 시작한다

코드구현

 

#include <iostream>
#include <vector>
#include <stack>
#include <list>
#include <queue>
using namespace std;


template<typename T, typename Container = vector<T>, typename Predicate = less<T>>
class PriorityQueue
{
public:
	void push(const T& data)
	{
		//우선 힙 구조부터 맞춰준다.
		_heap.push_back(data);

		//도장깨기 시작
		int now = static_cast<int>(_heap.size()) - 1;
		//루트 노드까지 시도
		while (now>0)
		{ 
			//부모 노드와 비교해서 더 작으면 패배
			int next = (now - 1) / 2;
			/*if (_heap[now] < _heap[next])
				break;*/
			if (_predicate(_heap[now], _heap[next]))
				break;
			//데이터 교체
			::swap(_heap[now], _heap[next]);
			now = next;
		}
	}
	void pop()
	{
		_heap[0] = _heap.back();
		_heap.pop_back();

		int now = 0;
		while (true)
		{
			int left = 2 * now + 1;
			int right = 2 * now + 2;

			//리프에 도달한 경우
			if (left >= _heap.size())
				break;

			int next = now;
			//왼쪽과 비교
			if (_predicate(_heap[next] , _heap[left]))
				next = left;

			//둘 중 승자를 오른쪽과 비교
			if (right < _heap.size() && _predicate(_heap[next], _heap[right]))
				next = right;

			//왼쪽,오른쪽 둘다 현재 값보다 작으면 종료
			if (next == now)
				break;

			::swap(_heap[now], _heap[next]);
			now = next;
		}
	}

	T& top()
	{
		return _heap[0];
	}

	bool empty()
	{
		return _heap.empty();
	}
private:
	Container _heap = {};
	Predicate _predicate = {};

};



int main()
{
	PriorityQueue<int, vector<int>, std::greater<int>> pq;//작은순서부터 출력

	pq.push(100);
	pq.push(300);
	pq.push(200);
	pq.push(500);
	pq.push(400);

	while (pq.empty() == false)
	{
		int value = pq.top();
		pq.pop();

		cout << value << endl;
	}

	return 0;
}