Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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 thanpush()
- 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
Question
The default container used by a priority_queue in C++ is?
vector
dequeue
list
array
Unless stated otherwise in initialization it uses a vector.
There are 2 containers in C++ STL library that can be used to make a priority queue => vector & deque.
With this article at OpenGenus, you must have the complete idea of Different ways to add elements in Priority queue in C++. Enjoy.