[C++] priority queue with Cpp

 

정의

• 우선순위 큐(priority queue)는 각 요소에 어떠한 우선순위가 추가로 부여되어 있는 컨테이너 
• container를 max heap으로 유지

 

특징

• 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 제공
• 일부 구현에서 두 요소의 우선 순위가 같으면 대기열에 포함된 순서에 따라 제공된다.
• 다른 구현에서 동일한 우선 순위를 가진 요소의 순서는 정의되지 않은 상태로 유지
• 데이터가 완벽히 정렬된 상태는 아니지만 최댓값은 빠르게 찾을 수 있음
• 연속적으로 데이터의 최댓값 또는 최솟값만 필요 시 
  • 상수가 큰 std::set 보다 훨신 효율적 동작

 

시간복잡도

• 힙 기반으로 -> 완전 이진 트리로 최소힙 또는 최대힙이 있다.
• 삽입, 삭제, 탐색, 수정에 대해 O(logN) 

 

int형 우선순위큐

• greater를 써서 오름차순
• less를 써서 내림차순
• 기본값 ->  내림차순이므로 단순하게 priority_queue<타입>을 쓰면 해당 타입에 대해 내림차순 설정
• 메서드는 stack과 동일

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq; // 오름차순
priority_queue<int> pq2; // 내림차순
priority_queue<int, vector<int>, less<int> > pq3; // 내림차순
int main(){
    for(int i = 5; i >= 1; i--){
        pq.push(i); pq2.push(i); pq3.push(i);
    }
    while(pq.size()){
        cout << pq.top() << " : " << pq2.top() << " : " << pq3.top() << '\n';
        pq.pop(); pq2.pop(); pq3.pop();
    }
    return 0;
}
/*
1 : 5 : 5
2 : 4 : 4
3 : 3 : 3
4 : 2 : 2
5 : 1 : 1
*/

 

 

구조체를 담은 우선순위큐

• int 뿐만 아니라 구조체(struct) 등 다른 자료구조를 넣어서 할 수도 있다.
• 구조체를 담은 우선순위를 보자

#include <bits/stdc++.h>
using namespace std;
struct Point{
    int y, x;
    Point(int y, int x) : y(y), x(x){}
    Point(){y = -1; x = -1;}
    bool operator < (const Point & a) const{
        return x > a.x;
    }
};

priority_queue<Point> pq;
int main(){
    pq.push({1, 1});
    pq.push({2, 2});
    pq.push({3, 3});
    pq.push({4, 4});
    pq.push({5, 5});
    pq.push({6, 6});
    cout << pq.top().x << "\n";
    return 0;
}
/*
1
*/

 

• 위의 코드를 보면 분명 < 연산자에 x > a.x를 했기 때문에 분명 내림차순으로 정렬되어 6이 출력이 되어야 하는데 1이 출력된다.
• 우선순위큐에 커스텀 정렬을 넣을 때 반대로 넣어야 하는 특징 때문

#include <bits/stdc++.h>
using namespace std;
struct Point{
    int y, x;
    Point(int y, int x) : y(y), x(x){}
    Point(){y = -1; x = -1; }
    bool operator < (const Point & a) const{
    	return x < a.x;
}
};
priority_queue<Point> pq;
int main(){
    pq.push({1, 1});
    pq.push({2, 2});
    pq.push({3, 3});
    pq.push({4, 4});
    pq.push({5, 5});
    pq.push({6, 6});
    cout << pq.top().x << "\n";
    return 0;
}
/*
6
*/

 

• 위에 보면 x > a.x가 x < a.x로 바뀐 모습
• 우선순위큐에 커스텀 정렬을 넣을 때는 반대라고 생각하면 된다.
• 가장 최소를 끄집어 내고 싶은 로직이라면 >
• 최대라면 <
• 아래처럼도 가능하다.

#include <bits/stdc++.h>
using namespace std;
struct Point{
	int y, x;
};
struct cmp{
	bool operator()(Point a, Point b){
		return a.x < b.x;
	}
};

priority_queue<Point, vector<Point>, cmp> pq;
int main(){
    pq.push({1, 1});
    pq.push({2, 2});
    pq.push({3, 3});
    pq.push({4, 4});
    pq.push({5, 5});
    pq.push({6, 6});
    cout << pq.top().x << "\n";
    return 0;
}
/*
6
*/