Priority_Queue
1. Priority_Queue란 무엇인가?
Priority_Queue는 Queue의 한 종류로 우선순위에 따라 정렬된 Queue이다.
어떤 원소가 삽입되면 주어진 우선순위에 맞춰서 Queue가 정렬되고, 삭제는 정렬된 Queue의 앞에서 이루어진다.
Heap로 구현되었기 때문에, O(log) 시간복잡도
2. priority_queue container 생성자와 연산자
template < typename T, typename Container = vector, typename Compare = less<typename Container::**velue_type> > class priority_queue;**
기본 생성자 형식 priority_queue < [Data Type] > [변수이름]; ex) priority_queue pq;
내부 컨테이너 변경 priority_queue < [Data Type], [Container Type] > [변수이름]; ex) priority_queue<int, deque > pq;
정렬 기준 변경 priority_queue < [Data Type], [Container Type], [정렬기준] > [변수이름]; ex) priority_queue, greater > pq;
3. C++ STL 우선순위 큐 라이브러리 기본 명령어
#include<queue>
- priority_queue<자료형, Container, 비교함수> 변수명
: 선언한 자료형 변수들을 비교함수에 따라 정렬하는
(비교함수에 greater<int> 넣어주면 오름차순으로 정렬)
Priority_Queue(우선순위 큐)를 선언
- priority_queue<자료형> 변수명
: 선언한 자료형 변수들을 내림차순에 따라 정렬하는 Priority_Queue(우선순위 큐)를 선언
- push(element) : Priority_Queue(우선순위 큐)에 원소 삽입 (삽입시 정렬됨)
- pop() : 맨 앞에 있는 원소 삭제
- top() : 맨 앞에 있는 원소를 반환
- empty() : Priority_Queue(우선순위 큐)가 비어있으면 true 아니면 false를 반환
- size() : Priority_Queue(우선순위 큐)의 크기를 반환
4. 사용 설명
우선순위 큐는 곧 Heap이다.
Heap은 Insertion과 Deletion에 최적화되어있는 자료구조 이다.
- 기본 우선순위 큐는 내림차순이다.
priority_queue<int, vector<int>, greater<int>> pq;
와 같이 사용시 오름차순 우선순위 큐이다.
less<자료형> : 내림차순
greater<자료형> : 오름차순
커스텀 비교 연산자 만들어 사용하기
우선순위 큐에는 구조체나 2차원 배열을 넣기도하고 2차원 벡터를 넣는 경우도 있다.
이때는 비교연산자를 포함한 구조체를 선언해주고, 그 구조체를 명시해주어야 한다.
비교연산자는 어떤 원소를 기준으로 정렬할 것인지를 명시해주면 된다.
struct cmp {
bool operator()(vector<int> a, vector<int> b){
return a[1] > b[1];
}
};
priority_queue<vector<int>,vector<vector<int>>, cmp> pq;
일 때,
return a[1] > b[1] : 오름차순 정렬
return a[1] < b[1] : 내림차순 정렬
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct cmp {
bool operator()(vector<int> a, vector<int> b){
return a[0] > b[0];
// a[1] > b[1]
// 0 3
// 2 6
// 1 9
// a[0] > b[0]
// 0 3
// 1 9
// 2 6
}
};
priority_queue<vector<int>,vector<vector<int>>, cmp> pq;
int main() {
vector<vector<int>> jobs = { {0, 3}, { 1, 9 }, { 2, 6 } };
pq.push(jobs[0]);
pq.push(jobs[1]);
pq.push(jobs[2]);
while (pq.empty() != true) {
cout << pq.top()[0] << " " << pq.top()[1] << endl;
pq.pop();
}
}
참고자료
댓글