알고리즘 복습)우선순위 큐/힙

우선순위 큐

 

우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙트리를 이용하여 구현한다. 기본적으로 내림차순(less)으로 설정되어 있지만, Predicate를 설정하여 오름차순(greater)으로 변경할수 있다.

 

힙트리

 

힙트리는 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다.

 

힙트리 구조

 

• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.(완전 이진 트리)

 

• 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야한다.

 

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

 

힙 트리 특징

 

• 부모 노드가 가진 값은 항상 자식 노드가 가진 값 보다 크다.

 

• 노드 개수를 알면, 트리 구조는 확정 지을 수 있다.

 

힙 트리 알고리즘

 

힙트리는 새로운 원소가 들어왔을때 혹은 루트노드가 제거 되었을때 힙트리의 구조를 갖추도록 설계 해야한다.

 

 

• 데이터 삽입

위와 같은 트리에서 30이라는 값을 트리에 삽입 하게 되면, 자식노드는 부모노드 보다 낮아야 되기 때문에

값을 변경해준다.

 

 

 

 

 

• 데이터 삭제

데이터 삭제의 경우 힙트리에서 루트 노드를 삭제하게 되면 루트 노드가 공석이 되며 그 자리는 마지막 노드가 채우게 되지만 힙트리의 노드는 부모노드가 자식노드보다 커야되므로 양쪽 자식중 큰 노드를 루트로 바꿔준다. 마찬가지로 부모노드와 자식노드를 비교해준다. 

 

 

 

 

 

우선순위 큐 구현

 

template<typename T,typename Container=vector<T>, typename Predicate = less<T>>
class PriorityQ
{
public:
	void push(const T&data)
	{
		_heap.push_back(data);

		int now = static_cast<int>(_heap.size())-1;
		
		while (now>0)
		{
			int parent = (now - 1) / 2;
			if (_pre(_heap[now] , _heap[parent]))break;
            //if(_heap[now]<_heap[parent])break;
			::swap(_heap[now],_heap[parent]);
			now = parent;

		}
	}
	void pop()
	{
		_heap[0] = _heap.back();
		_heap.pop_back();
	
		int now = 0;
		
		while (true)
		{
			int left = (now * 2) + 1;
			int right = (now * 2) + 2;
			int next = now;
			if (left >=(int) _heap.size()) break;
			//if (_heap[next] < _heap[left])
			if(_pre(_heap[next] , _heap[left]))
			{
				next = left;
			}
			//if (right<_heap.size()&&_heap[next] < _heap[right])
			if(right<_heap.size()&&_pre(_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 _pre = {};
};