Algo | C++ | priority Queue

Priority Queue

 

priority_queue < 자료형, 구현체, 비교연산자 >

#include <iostream>
#include <queue>

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;
}

위의 예서는 top이 1로 출력됨

우선순위큐에 커스텀 정렬을 넣을 때는 반대로 넣어야 함

가장 최소를 끄집어 내고 싶은 로직이면 >, 최대면 < 이런식으로

	bool operator < (const Point & a) const {
		return x < a.x;
	}

아래와 같은 방법도 가능함

#include <iostream>
#include <queue>

using namespace std;

struct Point{
	int y,x;
	Point(int y, int x) : y(y), x(x) {}
	Point() { y=-1; x=-1; }
};

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;
}