Introduction to Priority Queue

A priority queue is a container that provides constant time extraction of the largest element, at the expense of logarithmic insertion O(nlogn). It is similar to the heap in which we can add element at any time but only the maximum element can be retrieved. In a priority queue, an element with high priority is served before an element with low priority.
Following is the syntax for creating a priority queue :

priority_queue pq;

Functions of Priority Queue:

• push() : Inserts a new element in the priority queue. Its time complexity is O(logN) where N is the size of the priority queue. 
• pop() : Removes the largest element from the priority queue. Its time complexity is O(logN) where N is the size of the priority queue. 
• empty() : Returns true if the priority queue is empty and false if the priority queue has at least one element. Its time complexity is O(1). 
• size() : Returns the number of element in the priority queue. Its time complexity is O(1). 
• top() : Returns a reference to the largest element in the priority queue. Its time complexity is O(1). Sample program using priority_queue:

#include<bits/stdc++.h>
using namespace std;

int main ()
{
   priority_queue<int> pq;
   pq.push(30); // inserts 30 to pq, now top = 30
   pq.push(40); // inserts 40 to pq, now top = 40 ( maxinmum element)
   pq.push(90); // inserts 90 to pq, now top = 90  
   pq.push(60); // inserts 60 to pq, top still is 90    

   cout<<"Size is: "<<pq.size()<<"\n"; // print size of the priority queue

   while(pq.empty())
   {
      cout<<pq.top()<<"\n"; // print top element
      pq.pop(); // removes element from the priority queue
   }

   return 0;
}

Output:

Size is: 4

90
60
40
30