힙으로 구현한 우선순위 큐

힙으로 구현한 우선순위 큐 자료구조의 시간 복잡도는 삽입 삭제에서 O(logn) 이다.

우선순위에 따라 값이 정렬된다.

 

#include "iostream"
#include "vector"
#include "queue"
#include "algorithm"
#include "list"

using namespace std;

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

		// 도장깨기 시작!
		int now = static_cast<int>(_heap.size() - 1);

		// 루트까지 시도하다가 중간에 멈추면 break
		while (now > 0)
		{
			// 부모 노드와 비교해서 더 작으면 패배
			int next = (now - 1) / 2;

			/*if (_heap[now] < _heap[next])
			{
				break;
			}*/

			// _predicate 이라는 클래스, 구조체의 비교 연산 진행 오버라이딩 된거
			if(_predicate(_heap[now], _heap[next]))
				break;

			// 우선순위 높으니 데이터 교체하자
			::swap(_heap[now], _heap[next]);
			// 추가 된 노드의 인덱스 번호를 부모 노드 번호와 바꾼다.
			// 이러고 다시 while 문으로 도장깨기 시작! 반복
			now = next;
		}
	}

	void pop()
	{
		// 최상위 데이터 노드 빼고
		// 맨 꼴등 노드를 최상위로 올리고
		// 다시 밑으로 도장깨져버리기 시작 반복

		// 최상위에 있는거 뺀다는 개념. 이구문에서는 사실 덮어쓰는거임
		_heap[0] = _heap.back();
		// 여기서 마지막거 빼버리면 사실상 최상위 노드 빼고 거따가
		// 맨뒤에꺼 넣은거지 뭐
		_heap.pop_back();

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

			// leaf 에 도달했을 때
			// 이미 마지막 노드까지 갔는데 거기서 left 계산 또
			// 하면 당연히 _heap.size 보다 클 것이니까 이때는 나가자!
			// 참고로 size 이기 때문에 실제 노드의 번호보다 + 1 이라서
			// >= 한 것임 > 가 아니라
			if (left >= _heap.size())
				break;

			// now 는 나중에 2번 비교 후 바꿀거라서 지금 안바꾸기위해
			// next 라는 now 의 임시 저장 공간을 만든다.
			int next = now;

			// 일단 왼쪽이랑 비교
			/*if (_heap[next] < _heap[left])
			{
				next = left;
			}*/

			if (_predicate(_heap[next],_heap[left]))
			{
				next = left;
			}

			// next 가 바뀐거면 왼쪽 노드랑 오른쪽 노드의 비교
			// next 가 안바뀐거면 부모 노브랑 오른쪽 노드의 비교
			// 결국 비교는 해야한다.
			// 이때 오른쪽 노드가 존재하는지 부터 체크 size 로
			if (right < _heap.size() && _predicate( _heap[next],_heap[right]))
			{
				next = right;
			}

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

			// 왼쪽 노드이든 오른쪽 노드이든 더 우선순위가 높아서
			// 바뀐 값이 next 에 들어있으니 swap 진행
			::swap(_heap[now], _heap[next]);
			now = next;
		}

	}

	T& top()
	{
		// 최우선순위를 힙트리처럼 루트 노드(0번) 에 둘 거라서 
		return _heap[0];
	}

	bool empty()
	{
		return _heap.empty();
	}

private:
	Container _heap = {};
	// 이거의 연산자 오버라이딩 사용
	Predicate _predicate = {};
};

int main()
{
	// 실제 우선순위 큐
	// top pop 이 우선 순위에 따라 출력
	PriorityQueue<int, vector<int>, greater<int>> pq;

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

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

	// 낮은 순위를 먼저 출력하고 싶다면??

	priority_queue<int, vector<int>, greater<int>> pq2;

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

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

		cout << value << endl;
	}

	return 0;
}