Приоритетная очередь пар в C ++ с упорядочением по первому и второму элементу

Опубликовано: 16 Декабря, 2021

Очередь с приоритетом: Очередь с приоритетом - это расширение очереди, в котором элементы, связанные с приоритетом, и элементы с более высоким приоритетом выталкиваются первыми.

Приоритетная очередь может содержать элементы с различными типами данных, такими как целое число, пара целых чисел, пользовательский тип данных. Но есть одна общая черта: есть один элемент, который определяет приоритет элемента.
Таким образом, приоритетная очередь пар может иметь два типа упорядочения:

  • Упорядочено по первому элементу пары
  • Упорядочено вторым элементом пары

Приоритетная очередь, упорядоченная по первому элементу

В 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
Хотите узнать больше о лучших видео и практических задачах, ознакомьтесь с базовым курсом C ++ для базового и продвинутого уровней C ++ и курсом C ++ STL для базового уровня плюс STL. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .