우선순위 큐(Priority Queue)

큐 = Queue

- 먼저 집어넣은 데이터가 먼저 나오는 선입선출의 자료구조.

- 데이터를 아래에서 위로 쌓아올린다고 했을때 나가는 데이터는 맨 아래에 있는 데이터다.

- 큐에 데이터를 삽입하는 것을 Enqueue, 맨 앞의 데이터를 삭제하는 것을 Dequeue라고 한다.

- 연결 리스트, 벡터, 배열 등으로 구현 가능하며 <queue> STL도 존재함.

 

우선순위 큐 = Priority Queue

- 각 데이터에 우선순위를 두어서 우선순위가 가장 높은 데이터가 먼저 나가는 자료구조.

- 일반적으로 배열, 연결 리스트, 힙으로 구현하며 보통 삽입, 삭제 모두 O(logN)을 보장하는 힙으로 구현한다.

 

힙 = Heap

- 가장 크거나 작은 값을 찾기 위한 완전 이진 트리(중간에 빈 공간이 없는 트리)

- 데이터 삽입: 트리의 가장 끝의 자리에 노드를 삽입하여 부모랑 비교, 교환하는 과정을 거쳐 올라간다.

- 데이터 삭제: 루트노드를 삭제한 후, 가장 끝의 자리의 노드를 루트 노드로 하여 자식 노드들과 비교, 교환하는 과정을 거쳐 내려간다.

 

<queue> STL을 사용한 최대 우선순위 큐와 최저 우선순위 큐

 

#include<iostream>
#include<queue>
using namespace std;

priority_queue<int> maxpq; // 최대 우선순위 큐
priority_queue<int, vector<int>, greater<int>> minpq; // 최저 우선순위 큐

void SortQueue()
{
	if (!minpq.empty())
	{
		int maxpq_top = maxpq.top();
		int minpq_top = minpq.top();
		if (maxpq_top > minpq_top)
		{
			maxpq.pop();
			minpq.pop();
			maxpq.push(minpq_top);
			minpq.push(maxpq_top);
		}
	}
	cout << maxpq.top() << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int cmd;
	cin >> cmd;

	while (cmd--)
	{
		int num;
		cin >> num;

		if (maxpq.size() == minpq.size())
		{
			maxpq.push(num);
		}
		else
		{
			minpq.push(num);
		}

		SortQueue();
	}
}

백준 1655번 문제(https://www.acmicpc.net/problem/1655)