Priority Queue in C++

Priority Queue in C++

Introduction:

We have already come across Queues by concluding that they are linear data structures that follow FIFO (First-In-First-Out) approach. We had also discussed the syntax of queues and the operations associated with them. Let us now talk about the sub-section of queue i.e. Priority Queue.

Definition:

As the name suggests, priority queues are the abstract data types similar to queues where the element has some additional priority associated with it. The element with higher priority in the queue is preferred than the element with lower priority.

A priority queue is associated with the following properties-

There is priority associated with every element.

A higher priority element is dequeued before the lower priority element.

If two elements have the same priority then the priority is given to the element occurring first in the order.

Also, there are various operations associated with priority queues. They are:

1. insert(item, priority) : This is done to insert the element in the end of array in O(1) complexity.

• getHighestPriority(): This is done by linear searching in the array having element of the higher priority. This usually takes O(n) complexity.

• deleteHighestPriority(): This is done by pushing elements one subsequent position back by liner traversing over the array to search the item.

Let us now understand priority queues through the help of syntax and coding examples.

Syntax:

 template<
     class T,
     class Container = std::vector<T>,
     class Compare = std::less<typename Container::value_type>
 > class priority_queue; 

Here,

Template parameters are:

1. Container: It stores the elements in sequential order. It has additional semantics like:
2. front()
3. push_back()
4. pop_back()

Compare: It is used to compare the ordering in terms of strong and weak. The parameter of compare is defined as true if the first argument appears before the second argument in weak ordering.

Member Types	Definition
container_type	Container
Value_type	Value inside the container
Size_type	Size nature of the container
reference	Container elements reference
Constant reference	Constant referencing elements

Member Functions	Definition
Constuctor()	Constructs the priority queue
Destructor()	Removes the priority queue
Operator(=)	Assigns values in the queue

These are basic member types and functional definitions associated with the syntax of Priority queues.

Lets us now look at coding example to understand the priority queues in a better sense.

 #include<bits/stdc++.h>
 using namespace std; 
 int main() 
 { 
  priority_queue<int> Q;  
  Q.push(100);
  Q.push(200);
  Q.push(300);
  cout<<"Number of elements available in 'Q' :"<<Q.size()<<endl; 
  while(!Q.empty()) 
  { 
      std::cout << Q.top() << std::endl;  
      Q.pop(); 
  } 
  return 0; 
 }  

Output:

Explanation:

In the above code, we have created a single priority queue and the container contains 3 values 100,200, and 300 respectively. We could have also taken the value as inputs from the user. The next task is looping over the elements present in the queue and the queue which appears first will be printed first provided the loop iterates through the container until is not empty.

Note: We can also simply or define more priority queues depending upon the requirement. The approach will be as similar as shown in the above example.

Let us see how it is done in the coding example given below:

#include<bits/stdc++.h>
 using namespace std; 
 int main() 
 { 
 priority_queue<int> P;  
    priority_queue<int>Q;   
    P.push(23); 
    P.push(25);
    P.push(31);
    P.push(43);
    Q.push(51);  
    Q.push(64);
    Q.push(76);
    Q.push(85); 
    P.swap(Q); 
    std::cout << "P has following elements: " <<endl; 
    while(!P.empty()) 
    { 
       cout << P.top() <<endl; 
        P.pop(); 
    } 
    cout << "Q has following elements:" <<endl; 
     while(!Q.empty()) 
  { 
       cout << Q.top() <<endl; 
        Q.pop(); 
    } 
     return 0; 
 }   

Output:

Explanation:

In the above code, we have defined two priority queues P and Q to show how the priority concept works. We have defined two template priority queues P and Q having different integer arguments.

The operations push(), pop(), and swap() are well-discussed functions in the previous sections where the top is checked and popped out to facilitate the entry of the next element in the priority queue.

The logic is to iterate over both the priority queues P and Q and get the values assigned to them on a priority basis. We can visualize that the elements in P and Q are constantly being swapped if the values after comparing are found greater or small. If the greater element is found in any of the P or Q queues then it is swapped and printed on the console in ascending order.

Advantages of Priority Queues:

The advantages are listed below:

1. Priority queues are very easy to implement.

• Processes with different priorities can be easily handled using priority queues.

• Applications constituting different requirements in which highest or lowest elements may be needed, priority queues play a crucial role there.