PriorityQueue(우선순위 큐)

힙 구조로 이루어져 있어서 새로운 데이터가 추가되거나 삭제될 때 새롭게 정렬이 되어 출력 시 오름차순, 내림차순으로 출력이 된다.

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#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);
		
		// 인덱스가 교환을 할수록 작아지는데 0이되는건 최상위 부모 노드가 되었다는 것이니까 종료.
		while (now > 0)
		{
			int parent = (now - 1) / 2; // 부모 인덱스 구하기
			// (predicate = less 기준)현재위치가 부모의 값보다 작다면 정렬할 필요가 없으므로 종료.
			if (_predicate(_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; // 오른쪽 인덱스

			// 왼쪽 자식노드가 없다면 종료.
			if (left >= _heap.size())
				break;

			int next = now; // 변경할 수도 있는 인덱스

			// (predicate = less 기준)최상위의 값과 왼쪽 값을 비교하고 둘 중 더 큰값이 next에 저장되어 있을 것.
			if (_predicate(_heap[next], _heap[left]))
				next = left;

			// 오른쪽 자식노드가 있다면 next와 비교해서 더 큰 값을 next에 저장
			if (right < _heap.size() && _predicate(_heap[next], _heap[right]))
				next = right;

			// next == now라는 것은 자식노드가 모두 현재 위치보다 작은 것이고, 정렬된 것이므로 종료.
			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> priorityQueue;

	priorityQueue.push(1);
	priorityQueue.push(3);
	priorityQueue.push(2);
	priorityQueue.push(5);
	priorityQueue.push(4);

	while (priorityQueue.empty() == false)
	{
		int value = priorityQueue.top();
		cout << value << endl;
		priorityQueue.pop();
	}
}