Множественные сравнения в очереди приоритетов С++?

Priority Queue — это абстрактный тип данных, похожий на очередь, и каждый элемент имеет связанное с ним значение приоритета. Приоритет элементов в очереди приоритетов определяет порядок обслуживания элементов (т. е. порядок их удаления). Если в любом случае элементы имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди.

Что такое priority_queue STL в C++?

» Priority_queue » — это адаптер контейнера, который обеспечивает поиск самого большого элемента в постоянное время за счет логарифмической вставки и извлечения. Мы можем использовать предоставленную пользователем функцию сравнения, чтобы изменить порядок, например, использование std::greater приведет к тому, что наименьший элемент появится вверху.

Когда мы используем приоритетную очередь, мы в основном используем кучу в каком-то контейнере с произвольным доступом, преимущество которого заключается в том, что мы не можем случайно сделать данную кучу недействительной.

Приоритетная очередь с пользовательским компаратором

Пользовательские компараторы — это статические функции, которые используются для определения параметра, по которому будет сортироваться данный контейнер. Он определяет способ сортировки данного контейнера.

Если мы используем символ «>», то мы пытаемся отсортировать в порядке возрастания, иначе мы пытаемся отсортировать в порядке убывания, поскольку » > » вернет true, когда a> b ( a больше, чем b ), иначе он вернет ЛОЖЬ. Таким образом, обмен произойдет, если компаратор вернет значение true, иначе обмен не произойдет.

Давайте посмотрим программу и далее поймем, как эта концепция будет применяться.

С++

#include <bits/stdc++.h>

using namespace std;

// This template is used to print

// the given heap again and again

// irrespective of the given data type 

template <class T>

void printQueue(T& q)

{

    while (q.empty() == false) {

        cout << q.top() << " ";

        q.pop();

    }

    cout << endl;

}

// Here we are using a basic priority queue

// and sorting the queue in ascending order 

void samplepriorityqueue()

{

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

    for (int i = 0; i < 10; i++) {

        pq.push(i);

    }

    printQueue(pq);

}

// Here we are using the lambda comparator function

// to sort given priority queue in ascending order

void samplepriorityqueue1()

{

    auto compare = [](int left, int right) {

        return left < right;

    };

    priority_queue<int, vector<int>, decltype(compare)> pq(

        compare);

    for (int i = 0; i < 10; i++) {

        pq.push(i);

    }

    printQueue(pq);

}

// Here we are using a comparator function

// to sort the given priority queue.

// This comparator function can be extended

// to included several other features 

struct mycmp {

    bool operator()(int a, int b)

    {

        return a > b;

    }

};

void samplepriorityqueue2()

{

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

    for (int i = 0; i < 10; i++) {

        pq.push(i);

    }

    printQueue(pq);

}

// Driver code

int main()

{

    samplepriorityqueue();

    samplepriorityqueue1();

    samplepriorityqueue2();

    return 0;

}

Выход

0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9

Здесь мы видим, как компаратор используется для сравнения определенных типов данных и сортировки данных в соответствии с заданным нами компаратором.

Множественные сравнения в очереди приоритетов C++

Затем мы собираемся сделать несколько сравнений, используя очередь приоритетов для определенного пользователем типа данных, а затем мы собираемся отсортировать данные, которые были нам предоставлены.

Мы можем создать функцию компаратора, которая сравнивает более одного параметра и сортирует структуру данных на основе условий, предоставленных компаратором. Ниже представлена ​​реализация множественных сравнений в очереди приоритетов C++.

С++

#include <bits/stdc++.h>

using namespace std;

// Structure of a user defined data structure

struct jobs {

public:

    int priority;

    int processing;

    int arrivaltime;

    int proccessing_time;

    string job;

    jobs(int priority1, int processing1, int arrivaltime1,

         int proccessing_time1, string s1)

    {

        this->priority = priority1;

        this->processing = processing1;

        this->arrivaltime = arrivaltime1;

        this->proccessing_time = proccessing_time1;

        this->job = s1;

    }

};

// Here we are sorting based on the processing time

// if the priority is same and we are sorting

// in descending order if the priority is same.

// Else we are sorting in ascending order

// on the priority of the tasks given to us

struct compare {

    bool operator()(jobs a, jobs b)

    {

        if (a.priority == b.priority) {

            return a.processing < b.processing;

        }

        return a.priority > b.priority;

    }

};

// Driver code

int main()

{

    priority_queue<jobs, vector<jobs>, compare> pq;

    for (int i = 0; i < 10; i++) {

        jobs a(rand() % 11, i + 1, rand() % 3 + i,

               rand() % 5 + 3, "somejob" + to_string(i));

        pq.push(a);

    }

    while (pq.empty() == false) {

        jobs b = pq.top();

        pq.pop();

        cout << b.priority << " " << b.processing << " "

             << b.arrivaltime << " " << b.proccessing_time

             << " " << b.job << endl;

    }

    return 0;

}

Выход

0 9 10 5 somejob8
0 8 7 6 somejob7
3 3 2 4 somejob2
4 2 3 3 somejob1
6 1 1 6 somejob0
7 5 5 3 somejob4
7 4 5 4 somejob3
10 10 10 6 somejob9
10 7 7 5 somejob6
10 6 5 4 somejob5