[C++ STL] priority_queue

1. 완전이진트리 구조
2. c++에서의 구현은 배열로 되어있음
3. 직접 참조 불가능
배열연산자[ ] 로도 안되고 iterator로도 안됨
직접 참조해야하면 다른 자료구조로 바꾸는게 좋음
 
4. ps에서는 항상 값들을 정렬된 상태로 유지시켜야할때 사용
 
5. 보통 그리디에서 많이 쓰임
참고로 다익스트라를 떠올리면 됨.
다익스트라에서는 항상 가중치가 최소인 경로를 우선으로 작업을 해야하는데
해당 상황이 우선순위 큐를 쓰기에 적합한 상황임

---

우선순위 큐를 쓰는 가장 큰 이유는
 
1. 정렬 시간복잡도 O(logN)
2. 맨 위에꺼 pop 시간복잡도 O(1)
 
이 두 개이다
 
근데 우선순위 큐 쓸때 가장 중요한게 세번째 매개변수인 comparator / predicate 인데
이걸 정확하게 정의해줘야한다
 
그 이유는 Strict Weak Ordering 때문인데
이를 참고 하고 싶으면 이 포스트로 가라
 
https://mintuchel.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Strict-Weak-Ordering-%EC%A0%95%EB%A0%AC%EA%B8%B0%EC%A4%80 

[알고리즘] Strict Weak Ordering (정렬기준)

 

---

[priority_queue]

 

#include <queue>
using namespace std;

// 기본 내림차순
priority_queue<int> pq;

// 오름차순
priority_queue<int, vector<int>, greater<int>> pq;

 

 
자료구조에서 배운 그 우선순위 큐가 맞다.
C++에서 우선순위 큐는 배운거랑 모든게 똑같다.
 
1. 완전이진트리로 표현한다
-> 추가 삭제 할때마다 계속 정렬되어야하므로 O(logN) 인 트리구조로 표현하는 것
 
2. 구현은 배열로 한다 ( 필수는 아니지만 배열이 최고다 )
-> 노드기반으로 해도 되는데, 배열이 탐색속도가 더 빠르다. 
공간복잡도도 노드로 했을때보다 훠어어어어얼씬 뛰어나고
top()이나 부모자식노드를 접근하는데 가장 빠르기 때문이다!
 
3. 추가 삭제 될때마다 항상 자동으로 정렬된 상태를 유지함 O(logN)
 

---

[정렬기준]

 
3번째 인자로 정렬기준이 들어가는데
정렬기준 넣으려면 2번째 인자로 어떤 방식으로 구현할 지 넣어줘야함
그냥 원래 구현되어있는대로 vector 넣어주면 됨

// default 내림차순
priority_queue<int> pq;

// 오름차순
priority_queue<int, vector<int>, greater<int>> pq;

 
만약 커스텀 정렬기준(custom predicate)을 쓰고 싶을 시에는 
priority_queue 도 map과 동일하게 operator()를 오버로딩 하는 방식으로 정렬기준을 전달해줘야함.
방법은 map과 동일함.
구조체 안에 넣어 넘겨준다
 
근데 여기서 중요한게 vector 와 정렬기준이 다름.
만약 vector에서 아래와 같이 하면 오름차순으로 정렬됨.
return true 인 것이 우선순위가 높은 것이기 때문
 
근데 우선순위큐는 반대임
즉 아래와 같이 하면 내림차순으로 정렬됨.
vector 할때랑 반대로 적어놔야 원하는대로 정렬댐.
 

struct comp {
    // 오름차순 정렬
    bool operator()(const int& a, const int& b) const {
        return a < b;
    }
};

priority_queue<int, vector<int>, comp> pq;

 

---

[pair 정렬기준]

struct pq_comp {

	bool operator()(pair<int, int> obj1, pair<int, int> obj2) {
		if (obj1.first == obj2.first) {
        		// 내림차순 정렬
			return obj1.second > obj2.second;
		}
        	// 오름차순 정렬
		return obj1.first < obj2.first;
	}
    
};

 
pair<int,int> 를 저장하는 우선순위큐인데
만약 first 값이 다르면 더 작은 얘가 먼저오고
first 값이 같으면 second를 기준으로 정렬하는데
second 값이 높은 애가 우선순위가 높다고 판단된다.

 

---

[tuple 정렬 기준]

struct comp
{
    bool operator()(const tuple<int, int, int> &a, const tuple<int, int, int> &b)
    {
        auto [a1, a2, a3] = a;
        auto [b1, b2, b3] = b;

        // a3가 클수록 우선순위 낮음
        if (a3 != b3)
            return a3 > b3;
        // a1이 클수록 우선순위 낮음
        if (a1 != b1)
            return a1 > b1;
        // a2가 클수록 우선순위 낮음
        return a2 > b2;
    }
};

---

[Functions]

 
clear() 없음!
참고로 priority_queue는 clear 함수가 없다
그래서 다음과 같이 생성자로 초기화하는 방법밖에 없다