Приоритетная очередь пар в C ++ с упорядочением по первому и второму элементу
Очередь с приоритетом: Очередь с приоритетом - это расширение очереди, в котором элементы, связанные с приоритетом, и элементы с более высоким приоритетом выталкиваются первыми.
Приоритетная очередь может содержать элементы с различными типами данных, такими как целое число, пара целых чисел, пользовательский тип данных. Но есть одна общая черта: есть один элемент, который определяет приоритет элемента.
Таким образом, приоритетная очередь пар может иметь два типа упорядочения:
- Упорядочено по первому элементу пары
- Упорядочено вторым элементом пары
Приоритетная очередь, упорядоченная по первому элементу
В C ++, если элемент имеет форму пар, то по умолчанию приоритет элементов зависит от первого элемента. Следовательно, нам просто нужно использовать только приоритетную очередь пар.
C ++
// C++ implementation of the // priority queue of pairs // ordered by the first element #include <iostream> #include <queue> using namespace std; // Function to print the data of // the priority queue ordered by first void showpq( priority_queue<pair< int , int > > g) { // Loop to print the elements // until the priority queue // is not empty while (!g.empty()) { cout << g.top().first << " " << g.top().second << endl; g.pop(); } cout << endl; } // Driver Code int main() { priority_queue<pair< int , int > > p1; // Insertion of elements p1.push(make_pair(4, 5)); p1.push(make_pair(5, 4)); p1.push(make_pair(1, 6)); p1.push(make_pair(7, 3)); p1.push(make_pair(9, 4)); showpq(p1); return 0; } |
9 4 7 3 5 4 4 5 1 6
Примечание: если первый элемент некоторых пар будет одинаковым, то сравнение будет производиться на основе второго элемента.
Приоритетная очередь, упорядоченная по второму элементу (макс.)
Идея состоит в том, чтобы использовать структуру с концепцией перегрузки оператора в очереди приоритетов для упорядочивания пар по второму элементу.
Ниже приведена реализация очереди приоритетов, упорядоченная вторым элементом -
C ++
// C++ implementation of the // priority queue in which elements // are sorted by the second element #include <iostream> #include <queue> #include <vector> using namespace std; typedef pair< int , int > pd; // Structure of the condition // for sorting the pair by its // second elements struct myComp { constexpr bool operator()( pair< int , int > const & a, pair< int , int > const & b) const noexcept { return a.second < b.second; } }; // Function to show the elements // of the priority queue void showpq( priority_queue<pd, vector<pd>, myComp> g) { // Loop to print the elements // until the priority queue // is not empty while (!g.empty()) { cout << g.top().first << " " << g.top().second << endl; g.pop(); } cout << endl; } // Driver Code int main() { priority_queue<pd, vector<pd>, myComp> p1; p1.push(make_pair(4, 5)); p1.push(make_pair(5, 4)); p1.push(make_pair(1, 6)); p1.push(make_pair(7, 3)); p1.push(make_pair(9, 4)); // Function Call showpq(p1); return 0; } |
1 6 4 5 9 4 5 4 7 3
Приоритетная очередь, упорядоченная по второму элементу (мин.)
Идея состоит в том, чтобы использовать перегрузку оператора, чтобы реализовать приоритетную очередь, упорядоченную по ее второму элементу, с минимальным элементом наверху.
Ниже представлена реализация очереди приоритетов:
C ++
// C++ implementation of the priority // queue sorted by the second element // in the decreasing order #include <iostream> #include <queue> #include <vector> using namespace std; typedef pair< int , int > pd; // Structure of the operator // overloading for comparison struct myComp { constexpr bool operator()( pair< int , int > const & a, pair< int , int > const & b) const noexcept { return a.second > b.second; } }; // Function to print the elements // of the priority queue void showpq( priority_queue<pd, vector<pd>, myComp> g) { // Loop to print the elements // of the priority queue while (!g.empty()) { cout << g.top().first << " " << g.top().second << endl; g.pop(); } cout << endl; } // Driver Code int main() { priority_queue<pd, vector<pd>, myComp> p1; // Insertion of the elements p1.push(make_pair(4, 5)); p1.push(make_pair(5, 4)); p1.push(make_pair(1, 6)); p1.push(make_pair(7, 3)); p1.push(make_pair(9, 4)); showpq(p1); return 0; } |
7 3 5 4 9 4 4 5 1 6