priority_queue, sort에서의 정렬 방법

[gyurim]

priority_queue, sort에서의 정렬 방법

차이점

1.

• #include < algorithm > : sort에서는 greater가 내림차순
• #include < queue > : priority_queue의 sort에서는 greater가 오름차순

2.

• #include < algorithm > : sort에서는 cmp 함수를 만들 때, 인자의 왼쪽이 기준
• #include < queue > : priority_queue의 sort에서는 cmp 함수를 만들 때, 인자의 오른쪽이 기준

---

greater 사용하여 정렬

priority_queue

• priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
• priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

sort 함수

• sort(v.begin(), v.end()); // 오름차순
• sort(v.begin(), v.end(), greater()); // 내림차순

---

cmp 사용하여 정렬

1. first 큰 값부터 리턴, first 값이 같다면 second 값이 큰 값부터 리턴

priority_queue

• 기본적으로 priority queue 작동 자체가 first 값이 큰 값부터 리턴, 같다면 second 값이 큰 값부터 리턴이 된다.

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second < b.second; // pq는 오른쪽이 기준이기 때문에 second 내림차순 정렬 
    else return a.first < b.first; // first 내림차순 정렬 
}

sort 함수

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second > b.second; // sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬 
    else return a.first > b.first; // sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬 
}

2. first 큰 값부터 리턴, first 값이 같다면 second 값이 작은 값부터 리턴

priority_queue

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second > b.second; // second값 기준 오름차순
    else return a.first < b.first; // first값 기준 내림차순 (큰 값 우선)
}

sort 함수

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second < b.second;
		// sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬 
    else return a.first > b.first;
		// sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬 
}

3. first 작은 값부터 리턴, first 값이 같다면 second 값이 작은 값부터 리턴

priority_queue

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second > b.second; // second값 기준 오름차순
    else return a.first > b.first; // first값 기준 오름차순
}

sort 함수

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second < b.second;
		// sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬 
    else return a.first < b.first;
}