[0x17] 우선순위 큐

우선순위 큐

 

pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

원소의 추가 O(logN)

우선순위가 가장 높은 원소의 확인 O(1)

우선순위가 가장 높은 원소의 제거가 O(logN)

 

원소가 들어오면 정점의 왼쪽 자식부터 채워지기 때문에 항상 균형이 잘 맞는 이진 트리가 된다.

 

최대 힙, 최소 힙이 있다.

가장 크거나 작은값의 확인은 O(1)에 확인이 가능하지만 N번째의 크거나 작은값의 확인은 불가능하다.

 

STL priority_queue

 

기본적으로 최대 힙이다.

최소 힙으로 사용하려면 선언시 priority_queue<int, vector<int> greator<int>>로 선언하면 된다.

 

priority_queue에서 할 수 있는건 set에서도 할 수 있고 시간복잡도도 동일하지만 set보다 수행속도가 빠르고 공간을 적게 차지한다.

 

custom compare를 사용할 때 주의할점은 vector 등의 동적 배열에서의 sort custom compare는 컨테이너의 front가 의도한 대로의 최소/최대값이 되지만 우선순위 큐에서는 top이 컨테이너의 back이기 때문에 반대로 사용해야 한다.

pop을 하면 back이 튀어나오는 것이다.

그렇기 때문에 최대/최소값을 top에 두고싶으면 false를 반환해서 뒤로 계속 보내야 한다. (vector는 true)

내림차순 정렬시 앞의 원소보다 뒤의 원소보다 크다면 false, 오름차순 정렬시 true를 반환해야 한다.

 

sort와 우선순위 큐의 custom compare가 함수와 구조체로 다른 이유는 sort는 함수지만 우선순위 큐는 컨테이너이기 때문이다.

struct comp
{
	bool operator()(const int& a, const int& b)
	{
		// return a > b; 최소힙
    		// return a < b; 최대힙
	}
};

 

연습 문제

 

11286: 절댓값 힙

#include <bits/stdc++.h>
using namespace std;

struct comp
{
	bool operator()(const int& a, const int& b)
	{
		const int ta = abs(a);
		const int tb = abs(b);
		if (ta == tb) return a > b;
		return ta > tb;
	}
};

priority_queue<int, vector<int>, comp> q;
int n, x;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	while (n--)
	{
		cin >> x;
		if (x != 0)	q.push(x);
		else
		{
			if (!q.empty())
			{
				cout << q.top() << '\n';
				q.pop();
			}
			else cout << 0 << '\n';
		}
	}

	return 0;
}

 

custom compare 함수의 조건을 잘 생각해야한다. sort의 custom compare와는 조건이 반대다.

 

1715: 카드 정렬하기

#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<>> q;
int n, x, ans;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	while (n--)
	{
		cin >> x;
		q.push(x);
	}
	while (q.size() > 1)
	{
		int a = q.top();
		q.pop();
		int b = q.top();
		q.pop();
		ans += a + b;
		q.push(a + b);
	}
	cout << ans;

	return 0;
}

 

의외로 간단한 문제였는데 너무 생각을 짧게했는지 해답에 도달하지 못했음