우선순위 큐 (PriorityQueue)

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
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);

		//도장깨기 시작
		//static_cast<바꾸려고 하는 타입>(대상);
		// 현재 Index를 받는다.
		int now = static_cast<int>(_heap.size()) - 1;

		while (now > 0)
		{
			int next = (now - 1) / 2;

			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 >= (int)_heap.size())
				break;

			int next = now;

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

			//둘 중 승자를 오른쪽과 비교
			if (right < (int)_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>, greater<int>> pq;

	pq.push(700);
	pq.push(6000);
	pq.push(300);
	pq.push(500);
	pq.push(400);

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

		cout << value << endl;
	}
}

 

 

Push_back

 

void push(const T& data)
	{
		// 우선 힙 구조부터 맞춰준다.
		_heap.push_back(data);

		//도장깨기 시작
		//static_cast<바꾸려고 하는 타입>(대상);
		// 현재 Index를 받는다.
		int now = static_cast<int>(_heap.size()) - 1;

		while (now > 0)
		{
			int next = (now - 1) / 2;

			if (_predicate(_heap[now], _heap[next]))
				break;

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

now 에 현재 _heap의 사이즈를 받아온다.

now의 부모를 확인한 후, 비교하여 현재값이 부모값보다 크다면 스위칭하여 반복한다. 만약 비교하여 부모값보다 작다면 작업을 그만둔다.

 

Pop( )

	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 >= (int)_heap.size())
				break;

			int next = now;

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

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

			if (next == now)
				break;

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

최상단 값 (가장 큰 값)을 받아 출력하고 값을 최하단 값으로 복사한다.

그리고 최하단 노드를 없앤다.

 

최상단(최하단 복사된 값)이 자식과 비교하여 적정 자리에 위치시킨다.

비교할 때,

1. 비교하는 자식이 최종 노드인지를 확인한다.

2. 왼쪽 노드와 비교한다.

3. 오른쪽 노드와 비교한다.

4. 비교했는데 변화가 없다면(next == now), 최적 자리이기 때문에 작업을 마친다. 

5. 자리를 바꿔준다.