Different ways to add elements in Priority queue in C++

Priority Queue is an STL container. Primarily a container adapter which stores the greatest element at the top; a max-heap.
It is an adapter which uses a vector by default as an underlying container, but a deque can also be used. In this article, we have explored Different ways to add elements in Priority queue container in C++.

Library: queue

1. Using push()

void push (const value_type& val);
void push (value_type&& val);

• This method inserts a new element to the container and initializes it to val.
• In the background it calls two functions:
  • push_back of the underlying container (inserts the new element initialized with the given value).
  • push_heap, which makes the priority queue reorder the elements with respect to the newly added element.

#include <iostream> // std::cout
#include <queue>    // std::priority_queue

void printPriorityQueue(priority_queue<int> &pq)
{
    cout << "\n";
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << "\n";
}

int main()
{
    // default declaration assumes a vector container which stores the maximum element at top
    priority_queue<int> my_priority_queue;

    // insert elements to the priority_queue
    my_priority_queue.push(10);
    my_priority_queue.push(90);
    my_priority_queue.push(30);
    my_priority_queue.push(60);
    my_priority_queue.push(60);

    printPriorityQueue(my_priority_queue);

    return 0;
}

output:

90 60 60 30 10

Time Complexity: O(logN)

2. Using emplace()

template <class... Args> void emplace (Args&&... args);

• Inserts a new element to the priority queue which is constructed in-place.
• In the background it calls two functions:
  • emplace_back of the underlying container (inserts the new element initialized with the given value).
  • push_heap, which allows the priority queue to reorder the elements with respect to the newly added element.

*It might look identical to how push() works, but the two are NOT similar.

Difference:

• push() inserts a copy of an already created object into the priority queue as a parameter; it takes an object of the same type as that of the priority queue's element type.
• emplace() on the other hand constructs a new object in-place and adds it to the priority queue; it takes as parameters the parameters to create the object for the priority queue's element type.

Which one to use?

It depends:

• If you wish to add a copy of an existing object of the class to the container, use push().
• If you want to create a new object of the class, from scratch, use emplace().
• Duly note that emplace() is always as efficient/more efficient than push()
• Although, if dealing with primitive data types like int/float/char, etc, there is no significant trade-off between the two methods.

#include <iostream> // std::cout
#include <queue>    // std::priority_queue

void printPriorityQueue(priority_queue<int> &pq)
{
    cout << "\n";
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << "\n";
}

int main()
{
    // default declaration assumes a vector container which stores the maximum element at top
    priority_queue<int> my_priority_queue;

    // insert elements to the priority_queue
    my_priority_queue.emplace(10);
    my_priority_queue.emplace(90);
    my_priority_queue.emplace(30);
    my_priority_queue.emplace(60);
    my_priority_queue.emplace(60);

    printPriorityQueue(my_priority_queue);

    return 0;
}

output:

90 60 60 30 10

Time Complexity: O(logN)

3. Passing data to the constructor

• An existing container object (say a vector/array/deque) holding the data can be passed to the constructor of a priority queue to be initialized with its data.
• The constructor expects iterators pointing to the first and last positions in sequence which are to be considered for insertion.
• The range used is: [first, last); all the elements between first and last are added sequentially including the element pointed by the first but not the element (if any) pointed by the last

#include <iostream> // std::cout
#include <queue>    // std::priority_queue

void printPriorityQueue(priority_queue<int> &pq)
{
    cout << "\n";
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << "\n";
}

int main()
{
    // default declaration assumes a vector container which stores the maximum element at top
    vector<int> my_data = {10, 90, 30, 60, 60};
    priority_queue<int> my_priority_queue_one(my_data.begin(), my_data.end());

    // this inserts only the first 3 elements => {10,90,30}
    priority_queue<int> my_priority_queue_two(my_data.begin(), my_data.begin() + 3);

    // this inserts the following 3 elements => {30,60,60}
    priority_queue<int> my_priority_queue_three(my_data.begin() + 2, my_data.begin() + 5);

    printPriorityQueue(my_priority_queue_one);
    printPriorityQueue(my_priority_queue_two);
    printPriorityQueue(my_priority_queue_three);

    return 0;
}

output:

90 60 60 30 10
90 30 10
60 60 30

Time Complexity: O(NlogN)

A more complex example

• In C++ the default priority queue stores the greatest element at the top.
• This example illustrates a custom approach to store objects of a class in a priority queue with respect to a custom comparison function.

#include <iostream> // std::cout
#include <queue>    // std::priority_queue

class Student
{
    int roll_no;
    string name;

public:
    Student(int roll_no, string name)
    {
        this->roll_no = roll_no;
        this->name = name;
    }

    int getRollNo() const
    {
        return this->roll_no;
    }

    void print() const
    {
        cout << "\n"
             << "Roll no.: " << this->roll_no << ", Name: " << this->name;
    }
};

struct myCompare
{
    // ensures that the smallest roll_no is at the top of the priority queue
    bool operator()(const Student &a, const Student &b) const
    {
        return a.getRollNo() > b.getRollNo();
    }
};

void printPriorityQueue(priority_queue<Student, vector<Student>, myCompare> &pq)
{
    cout << "\n";
    while (!pq.empty())
    {
        pq.top().print();
        pq.pop();
    }
    cout << "\n";
}

int main()
{
    Student obj1(1, "elephant");
    Student obj2(2, "lion");
    Student obj3(3, "whale");
    Student obj4(4, "dog");
    Student obj5(5, "tiger");
    Student obj6(6, "dolphin");
    Student obj7(7, "sparrow");

    vector<Student> students = {obj1, obj2, obj3, obj4, obj5, obj6, obj7};

    // inserting by passing the iterators of students vector to the constructor
    priority_queue<Student, vector<Student>, myCompare> my_priority_queue(students.begin(), students.end());

    Student obj(8, "monkey");
    // inserting an already existing object by using push
    my_priority_queue.push(obj);

    // inserting by passing the arguments of the constructor of class Student
    my_priority_queue.emplace(9, "cat");

    printPriorityQueue(my_priority_queue);

    return 0;
}

output:

Roll no.: 1, Name: elephant
Roll no.: 2, Name: lion
Roll no.: 3, Name: whale
Roll no.: 4, Name: dog
Roll no.: 5, Name: tiger
Roll no.: 6, Name: dolphin
Roll no.: 7, Name: sparrow
Roll no.: 8, Name: monkey
Roll no.: 9, Name: cat

With this article at OpenGenus, you must have the complete idea of Different ways to add elements in Priority queue in C++. Enjoy.