이전에 배웠던 vector, stack, queue, deque가 연속된 위치에 일렬로 데이터를 세워둔 것과 달리 priority_queue는 이진 트리 구조를 갖는 heap을 이용해서 데이터를 저장한다. 내부 구조는 달라도 queue와 비슷하게 pop, push 연산을 지원한다.
priority_queue는 주로
1)원소를 추가하는 연산이 있으면서
2)우선순위 큐 내의 원소 중 최댓값(또는 최솟값)을 빠르게 구해야 하고,
3)해당 원소를 삭제하는 연산이 있는 경우 주로 사용한다.
이때 최댓값만을 구할 수 있으며 이외의 값들은 정렬되어있지 않고, 접근할 수도 없다는 점을 주의해야 한다.
우선순위 큐는 PQ.top()에 최댓값(또는 최솟값) 원소가 오도록 유지하면서 새로운 원소의 삽입과 최댓값(또는 최솟값) 원소의 삭제를 O(logn)에 처리할 수 있는 자료구조이다.
우선순위 큐의 실제 구현은 이진 트리 구조를 갖는 heap으로 구현이 되어있지만, 우선순위 큐를 떠올릴 때 굳이 이진 트리를 떠올릴 필요는 없다. 따라서 그냥 push를 이용해 PQ 내에 원소를 삽입할 수 있고 top에 최댓값이 있으며 최댓값 삭제 연산을 지원하는 stack 느낌의 이미지를 떠올리면 된다.
생성자)
1. priority_queue<T> PQ;
T의 비교 연산자에 대해 최댓값이 top에 오도록 하는 우선순위 큐를 생성한다.
이를 이용하면 비교 연산자가 정의된 사용자 정의 자료형을 만들어서 priority_queue<Info> 처럼 사용할 수 있다. 이때 Info의 비교 연산자 기준으로 가장 큰 원소가 PQ.top()에 위치한다.
2. priority_queue<T> PQ(v.begin(), v.end());
시작 iterator와 끝 iterator를 받아와서 [start, end) 범위의 원소를 갖는 우선순위 큐를 생성한다.
3. priority_queue<T, vector<T>, Cmp> PQ(cmp); // 단, cmp의 자료형은 Cmp
비교 자료형을 템플릿에 넣어준 뒤 선언된 비교 연산자를 매개변수로 넣어줘서 우선순위 큐의 비교함수로 이용한다.
이때 Cmp가 ()연산자가 정의된 구조체(= Functor)라면 알아서 자료형에 정의된 ()연산자를 이용해서 매개변수를 생략해도 되지만, 람다식(또는 전역함수)이라면 타입만으로 ()연산자를 알아서 정의할 수 없기 때문에 매개변수로 객체를 넣어줘야 한다.
멤버 함수)
int main() {
fastio;
priority_queue<int> PQ1; // max_heap
for (auto& i : { 3, 1, 4, 1, 5 }) PQ1.push(i); // PQ1 = [5(top), 4, 3, 1, 1]
while (!PQ1.empty()) {
cout << PQ1.size() << ' ' << PQ1.top() << '\n';
PQ1.pop();
}
cout << '\n';
priority_queue<int, vector<int>, greater<int>> PQ2; // min_heap으로 원소들이 오름차순으로 나열된다
for (auto& i : { 3, 1, 4, 1, 5 }) PQ2.push(i); // PQ2 = [1(top), 1, 3, 4, 5]
while (!PQ2.empty()) {
cout << PQ2.size() << ' ' << PQ2.top() << '\n';
PQ2.pop();
}
}
O(logn)에 처리할 수 있는 자료구조이다.
정렬 기준)
priority_queue<자료형, 컨테이너, 비교 자료형>
ex) priority_queue<T, vector<T>, less <T>>
priority_queue<int> pq; 처럼 자료형만 입력하면 기본적으로 내림차순으로 정렬된다.
<참고>
비교 자료형은 비교 함수 객체의 자료형을 의미한다. 이때 비교 함수 객체란 () 연산자를 지원하고, 두 값을 매개변수로 받아서 strict weak ordering을 만족하는 결과를 bool 자료형으로 반환하는 객체를 의미한다.
strict weak ordering이란 비교 함수 F가 다음의 네 가지 조건을 만족하면 된다.
1. 비반사성(irreflexivity) : F(a, a)는 항상 거짓
2. 비대칭성(asymmetry) : F(a, b)가 참이라면 F(b, a)는 항상 거짓
3. 추이성(transitivity) : F(a, b)가 참이고 F(b, c)가 참이라면 F(a, c)는 항상 참
4. 비비교성의 추이성(transitivity of incomparability) : F(a, b), F(b, a)가 거짓이고 F(b, c), F(c, b)가 거짓이면 F(a, c), F(c, a)는 항상 거짓
priority_queue의 정렬 기준을 지정하는 세 가지 방법
1. 자료형 bool operator < 정의
struct Info {
int val;
bool operator< (const Info& i) const {
return val > i.val; } };
int main() {
fastio;
priority_queue<Info> PQ;
PQ.push(Info{1}); PQ.push(Info{2});
PQ.push(Info{3}); PQ.push(Info{4});
while (PQ.size()) {
auto cur = PQ.top(); PQ.pop();
cout << cur.val << '\n'; // 1 2 3 4
}
}
우선순위 큐 템플릿은 priority_queue<T, Container = vector<T>, Compare = less<T>>로 구현되어있다.
즉, priority_queue<T>를 사용하면 less<T>에서 자료형의 < 연산자를 기준으로 가장 큰 값이 PQ.top()에 위치하게 된다.
struct나 class를 이용해 사용자 정의 자료형을 만들고 < 연산자를 정의해주면 비교 함수 객체를 구현할 필요 없이 간단히 정렬 기준을 지정할 수 있다.
정렬 결과가 헷갈릴 수 있는데, < 연산자의 정의대로 원소를 비교했을 때 가장 큰 값이 PQ.top()에 위치한다는 것만 기억하면 된다.
2. Functor 이용
struct Cmp {
bool operator() (const int& a, const int& b) const {
return a > b; // 가장 작은게 최댓값 }
};
int main() {
fastio;
priority_queue<int, vector<int>, Cmp> PQ;
PQ.push(1); PQ.push(2);
PQ.push(3); PQ.push(4);
while (PQ.size()) {
auto cur = PQ.top(); PQ.pop();
cout << cur << '\n'; // 1 2 3 4
}
}
1번 방법은 새로운 자료형을 직접 정의해서 사용하기 때문에 기존의 자료형을 그대로 사용할 수 없다. 만약 기존 자료형을 그대로 사용하고 싶다면 비교 함수 객체를 직접 정의해서 사용해야한다.
위의 예시는 () 연산자가 정의된 구조체(= Functor)를 비교 함수 객체로 이용한 코드이다.
template 인자로 들어가는 비교 자료형은 비교 함수 객체의 자료형인 Cmp가 되고, 자료형만으로 () 연산자의 정의를 가져올 수 있기 때문에 PQ의 생성자로 Cmp() 등을 따로 넘겨줄 필요가 없다.
priority_queue template 인자의 기본형으로 들어가는 less<T>도 Functor로 구현되어있다.
만약 자료형의 > 연산자를 기준으로 정렬했을 때 가장 오른쪽에 오는 값이 PQ.top()에 오길 원하면(= 내림차순) greater<T> Functor를 세 번째 인자로 넣어주면 된다.
1번과 2번의 차이를 명확하게는 모르겠지만 우선 이렇게 하는구나 정도로 알고 넘어가자
<코드 예시>
struct compare{
bool operator() (pair<char, int> a, pair<char, int> b){
return a.second<b.second;}
};
int main(int argc, char **argv){
fastio;
vector<pair<char,int>> v;
for(int i=0; i<5; i++){
v.push_back(pair<char,int>('a'+i, 5-i));
}
priority_queue<pair<char,int>> pq_max;
priority_queue<pair<char,int>, vector<pair<char,int>>, greater<pair<char,int>>> pq_min;
priority_queue<pair<char,int>, vector<pair<char,int>>, greater<pair<char,int>>> pq_custom;
for(int i=0; i<5; i++){
pq_max.push(v[i]);
pq_min.push(v[i]);
pq_custom.push(v[i]);
}
cout << "내림차순" << endl;
for (int i = 0; i < 5; i++)
{
cout << pq_max.top().first << " : " << pq_max.top().second << endl;
pq_max.pop();
}
cout << "오름차순" << endl;
for (int i = 0; i < 5; i++)
{
cout << pq_min.top().first << " : " << pq_min.top().second << endl;
pq_min.pop();
}
cout << "사용자 설정" << endl;
for (int i = 0; i < 5; i++)
{
cout << pq_custom.top().first << " : " << pq_custom.top().second << endl;
pq_custom.pop();
}
}
<백준>
11286번)
절댓값 min heap: 0을 제외한 정수를 push한다. 0을 입력하면 절댓값이 작은 순으로 나온다. 절댓값이 작은 수가 여러 개면 작은 수부터 나온다.
struct Cmp{
bool operator() (int a, int b){
if (abs(a) != abs(b)) return abs(a)>abs(b);
return a>b;
} //여기서 절댓값 a,b를 처리한다.
};
int main(){
fastio;
priority_queue<int, vector<int>, Cmp> PQ;
int n; cin>>n;
while(n--){
int t; cin>>t;
if (t) PQ.push(t);
else{
if(PQ.empty()) cout<<0<<'\n';
else cout<<PQ.top()<<'\n'; PQ.pop();
}
}
}
1655번)
최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.
최대 힙의 최대 원소는 최소 합의 최소 원소보다 작거나 같다.
max_heap이 아래에, min_heap이 위에 있는 모래시계 구조를 생각하면 된다.
만약 max큐의 top값이 min큐의 top값 보다 클 시, max큐와 min큐의 top 값을 swap 해줘서 max 큐의 top 값에
전체수가 짝수일 시 작은 수를 출력, 전체수가 홀수일 시 중간 값을 출력 조건을 맞춰준다.
int main(){
fastio;
int n; cin>>n;
priority_queue<int> PQ1; //max_heap
priority_queue<int, vector<int>, greater<int>> PQ2; //min_heap (오름차순 정렬)
while(n--){
int t; cin>>t;
if (PQ1.size() > PQ2.size()) PQ2.push(t); // k+1, k 일 때
else PQ1.push(t);
if(PQ1.size() && PQ2.size() && PQ1.top() > PQ2.top()){ //max_heap의 가장 큰 수가 min_heap의 가장 작은 수보다 커질 경우 swap 필요
int t1=PQ1.top(); PQ1.pop();
int t2=PQ2.top(); PQ2.pop();
PQ1.push(t2); PQ2.push(t1);
}
cout<<PQ1.top()<<'\n';
}
}
2696번)
int main(){
fastio;
int n;
cin>>n;
while(n--){
int num;
cin>>num;
priority_queue<int> PQ1;
priority_queue<int, vector<int>, greater<int>> PQ2;
vector<int> ans;
for(int i=0; i<num ;i++){
int a;
cin>>a;
if (PQ1.size() > PQ2.size()) PQ2.push(a);
else PQ1.push(a);
while (PQ1.size() && PQ2.size() && PQ1.top() > PQ2.top()) {
int t1 = PQ1.top(); PQ1.pop();
int t2 = PQ2.top(); PQ2.pop();
PQ1.push(t2); PQ2.push(t1);
}
if (~i & 1) ans.push_back(PQ1.top());
}
cout<<ans.size()<<'\n';
for(int i=0; i<ans.size(); i++){
cout<<ans[i]<<' ';
if(i==ans.size() -1 ||(i+1)%10 ==0 ) cout<<'\n'; //10개씩 줄바꿈해주기
}
}
}
'백준일지' 카테고리의 다른 글
| [C++] STL 자료구조: Set, Map (1) | 2024.05.07 |
|---|---|
| [C++] STL 자료구조: List (0) | 2024.05.02 |
| [C++] STL 자료구조: Deque (1) | 2024.04.07 |
| [C++] STL 자료구조: Queue (0) | 2024.04.03 |
| [C++] STL 자료구조: stack (0) | 2024.03.31 |
