Different Ways to Initialize Priority queue in C++


C++ STL comes with a ton of pre-written code for data structures and algorithms and most of it is not known to most of us therefore in this article i will be teaching you about one of the very useful data structure available in C++ stl called priority queue and also i will showing different ways to initialize it.

Priority Queue

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority, value of element itself is considered for priority.If elements with the same priority occur, they are served according to their order in the queue .Elements can be inserted in any order in queue but only the greatest element can be retrieved from queue in constant time O(1).In context priority queue is similar to max heap , although we can also create the priority queue such that top element of the priority queue always hold the smallest element of the queue in that way it will resemble min heap.The time complexity for inserting and deleting element from priority queue is O(log(n)) , for searching it is O(n) and for retrieving greatest element it is O(1) . We will look at both of these priority queues and how to initialize and use them.

1

Different ways of initializing a priority queue

We can either create a max heap or min heap from the priority queue, although syntax for creating them is very different and in further sections i will show you the difference in syntax by showing you the code for creating both of these queues.

  1. Max heap using priority queue
  2. Min heap using priority queue
  3. Initilization with vector and array

1. Max heap using priority queue

In priority queue based on max heap - top of the queue always stores the maximum element , syntax for creating priority queue based on min heap is shown below:

Code

#include <iostream>
#include<queue>
// remember to include queue to use priority queue

using namespace std;

int main()
{
  priority_queue <int> pq;
  // syntax for creating a priority queue based on max heap

      pq.push(10); 
      pq.push(30); 
      pq.push(20); 
      pq.push(5); 
      pq.push(1);

  cout<<"The priority queue based on max heap is\n" ;



      while (!pq.empty()) 
      { 
        cout<< pq.top()<<endl; 
        pq.pop(); 
      }

       return 0;
}

Output

The priority queue based on max heap is:
30
20
10
5
1

2. Min heap using priority queue

In priority queue based on min heap top of the queue always stores the minimum element , syntax for creating priority queue based on min heap is shown below.

Code

#include <iostream>
#include<queue>
// remember to include queue to use priority queue

using namespace std;

int main()
{
  priority_queue <int,vector<int>,greater<int>> pq ;

      pq.push(10); 
      pq.push(30); 
      pq.push(20); 
      pq.push(5); 
      pq.push(1);

  cout<<"The priority queue based on min heap is\n" ;


      while (!pq.empty()) 
      { 
        cout<< pq.top()<<endl; 
        pq.pop(); 
      }

       return 0;
}

Output

The priority queue based on min heap is:
1
5
10
20
30

3.Initilization with vector and array

we can also initialize priority queue of min heap or max heap using vector or array ,code for which is given below :

#include <iostream>
#include<queue>
// remember to include queue to use priority queue

using namespace std;

int main()
{

  vector<int> vec( { 15 , 25 , 35 } ) ;

  int arr[3] = { 12 , 16 , 18 } ;

  priority_queue <int> pq( vec.begin() , vec.end() );
  priority_queue <int> pq2( arr , arr+3 ) ;

      pq.push(10); 
      pq.push(30); 
      pq.push(20); 
      pq.push(5); 
      pq.push(1);

  cout<<"The priority queue with vector initilization is:\n" ;

  while (!pq.empty()) 
  { 
        cout<< pq.top()<<endl; 
        pq.pop(); 
  }

  cout<<"The priority queue with array initilization is:\n" ;


  while (!pq2.empty()) 
  { 
        cout<< pq2.top()<<endl; 
        pq2.pop(); 
  }

       return 0;
}

Output

The priority queue with vector initilization is:
35
30
25
20
15
10
5
1
The priority queue with array initilization is:
18
16
12

Questions

To make sure that you understand the concepts answer these queshions:

Can we access elements randomly from a priority queue ?

Yes
No
Sometimes
None of the above
We cannot access elements randomly from a priority we can only access the top element from priority queue in constant time.

which element exist at top in priority queue representing min heap and max heap ?

greatest and smallest
smallest and greatest
greatest and greatest
smallest and smallest
For min heap based priority we can access the minimum element from the top of the queue and for max heap based priority queue we can access the maximum element from the top of the queue.

What is time complexity for inserting and deleting elements from priority queue ?

O(log(n) ) for inserting and O(n) for deleting
O(n) for inserting and O(log(n)) for deleting
O(log(n)) for inserting and O(log(n)) for deleting
O(n) for inserting and O(n*n) for deleting
Time complexity for both inserting and deleting element from priority queue is O(log(n))