Wednesday, October 12, 2022
HomeWordPress DevelopmentA number of comparisons in a C++ precedence queue?

A number of comparisons in a C++ precedence queue?


What’s a Precedence Queue?

A Precedence Queue is an summary information kind that’s just like a queue, and each aspect has some precedence worth related to it. The precedence of the weather in a precedence queue determines the order by which components are served (i.e., the order by which they’re eliminated). If in any case, the weather have the identical precedence, they’re served as per their ordering within the queue.

To study extra about precedence queue, discuss with the article on “Introduction to Precedence Queue“.

What’s priority_queue STL in C++?

A ‘priority_queue‘ is a container adaptor that gives us with a relentless time lookup of the biggest aspect on the expense of logarithmic insertion and extraction. We are able to use a user-provided examine perform to alter the order e.g. utilizing std::larger<T> would trigger the smallest aspect to seem on the high.

After we are utilizing the precedence queue we’re mainly utilizing a heap in some random entry container, which has the good thing about not having the ability to by chance invalidate the given heap.

Precedence Queue with a Customized Comparator 

Customized comparators are static features which might be used to outline the parameter on which the given container goes to be sorted. It determines the way in which by which the given container goes to be sorted. 

If we use a ‘>’ image then we are attempting to type within the ascending order else we are attempting to type within the descending order as ‘>‘ will return true when a > b (a is bigger than b) else it would return false. So a swap will happen if the comparator goes to return true else no swap goes to happen. 

Let’s see a program and additional perceive how this idea goes to be utilized.

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

template <class T>

void printQueue(T& q)

{

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

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

        q.pop();

    }

    cout << endl;

}

  

void samplepriorityqueue()

{

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

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

        pq.push(i);

    }

    printQueue(pq);

}

  

void samplepriorityqueue1()

{

    auto examine = [](int left, int proper) {

        return left < proper;

    };

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

        examine);

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

        pq.push(i);

    }

    printQueue(pq);

}

  

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);

}

  

int predominant()

{

    samplepriorityqueue();

    samplepriorityqueue1();

    samplepriorityqueue2();

    return 0;

}

Output

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 

Right here we see how the comparator is used to match the outlined datatypes and type the info based on the comparator that we’ve got given.

A number of Comparisons in a C++ Precedence Queue

Subsequent, we’re going to make a number of comparisons utilizing the precedence queue on a user-defined information kind after which we’re going to type the info that has been given to us.

We are able to construct a comparator perform that compares multiple parameter and type the info construction based mostly on the situations offered within the comparator. Beneath is an implementation of a number of comparisons in C++ precedence queue.

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

struct jobs {

public:

    int precedence;

    int processing;

    int arrivaltime;

    int proccessing_time;

    string job;

    jobs(int priority1, int processing1, int arrivaltime1,

         int proccessing_time1, string s1)

    {

        this->precedence = priority1;

        this->processing = processing1;

        this->arrivaltime = arrivaltime1;

        this->proccessing_time = proccessing_time1;

        this->job = s1;

    }

};

  

struct examine {

    bool operator()(jobs a, jobs b)

    {

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

            return a.processing < b.processing;

        }

        return a.precedence > b.precedence;

    }

};

  

int predominant()

{

    priority_queue<jobs, vector<jobs>, examine> 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);

    }

  

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

        jobs b = pq.high();

        pq.pop();

        cout << b.precedence << " " << b.processing << " "

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

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

    }

    return 0;

}

Output

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments