<자료구조> 우선순위 큐

우선순위 큐(Priority Queue) : 내부구조는 heap으로 구현되어있으며 주로 다익스트라, 그리디 등에 쓰입니다.
다음 코드 처럼 greater 를 써서 오름차순, less를 써서 내림차순으로 바꿀 수 있습니다.

 

 

최소힙, 최대힙

정렬하는 것은 이 최소힙, 최대힙을 머리속으로 생각하면 될 것 같다.

 

 

 

방식

---

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

 

* 우선순위 큐에서는 커스텀정렬 넣을때 반대로 넣는게 특징이다.

 

 

 

 

 

 

 

활용 코드 1

---

#include<bits/stdc++.h>
using namespace std;
// priority_queue<자료형, 구현체, 비교연산자> 
priority_queue<int, vector<int>, greater<int>> pq; // 오름차순 
// priority_queue<int, vector<int>, less<int>> pq; // 내림차순 
 

int main()
{	
	pq.push(5);
	pq.push(4);	
	pq.push(3);
	pq.push(2);
	pq.push(1);
	cout << pq.top() << "\n";
	return 0;
}

/*
1
*/

 

 

 

 

활용 코드 2(구조체 커스텀 정렬 활용)

---

#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;		
	//}
	
	// 우선순위 큐에서는 반대로 해서 얘가 내림차순이됨 
	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({5, 6});
	cout << pq.top().x << "\n";
	return 0;
}

/*
6
*/

 

 

 

 

활용 코드 3

---

#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({5, 6});
	cout << pq.top().x << "\n";
	return 0;
}

/*
6
*/