How to Implement a Priority Queue in C++

A priority queue is a container in the STL. It is similar to queue except for the fact that each element of the priority queue has certain priority and when we pop elements from the priority queue, the elements with the highest priority are popped first. Like the priority queue, there are 10 different types of containers in STL. A container is an object that stores data. The STL containers are implemented with the help of template classes hence customizing it to hold different types of data is easy. In this post, we will discuss the Priority queue and concepts related to it in detail. Following pointers will be covered in this Priority Queue in C++ article,

• Components of STL
• Heaps and Priority Queue
• Printing all the elements of Priority Queue in C++

Moving on with this article on Priority Queue in C++

Components of STL

STL consists of template classes and functions which can be used as a standard approach for storing and processing data. Let’s discuss the components of the STL

Containers- There are 10 types of containers defined in STL and these are grouped into 3 categories. Out of these 3, Priority queues belongs to the category of the derived container. Each container class has its own set of functions that can be used to manipulate the data.

Algorithm– An algorithm is a method used to process the data present in the container object. STL provides many different types of Algorithms which can be used in initialising, searching, sorting, merging, copy. Algorithms are implemented with the help of template functions.

Iterator- An iterator is an object which points towards an element in the container. Iterators can help use in moving through the contents of a container. Iterators are like pointers which can be incremented and decremented. It acts as a link between the algorithm and the container. Iterators are used for manipulating the data stored in a container.

Moving on with this article on Priority Queue in C++

Heaps and Priority Queue

As we saw earlier Priority Queue belongs to the category of derived containers. Other members of this category are stack and queue. These derived containers are also known as container adaptors.

Stack, queue and priority queue are known as derived containers as they are made from different sequence containers. These containers do not support any type of iterators they are not used for data manipulation.

What exactly is a priority queue?

In simple words, it is a container which we used to store data. Each element of the stored data is assigned some priority which can help us in storing data in a logical order.
Syntax: priority_queue variable_name;

It is important to include a header file in the program in order to use a priority queue.

For example, if we add 2, 10, 30, 5, 6 in our priority queue using push function and then pop the elements using pop function the output will be 30, 10, 6, 5, 2.

Okay, so now we know the purpose or the use of priority queue. But how did it know if 30 > 10? Is it doing some kind of sorting? At this point Heaps come into the picture. To learn about heaps in detail refer to this article.

Heaps- Heaps are tree-like structures. Based on how the child elements nodes are arranged in a heap with respect to the parent nodes, heaps are subdivided into 2 parts

1. Min Heap- In Min Heap, the value of the parent node is less than or equal to the value of the child nodes.

2. Max Heap- In Max Heap, the value of the parent node is greater than or equal to the value of the child nodes.

Note- Priority queue does not sort the elements using some sorting algorithm instead it stored the data in the form of a heap.

Moving on with this article on Priority Queue in C++

Printing all the elements of a priority queue

After understanding the fundamentals of the priority queue, let’s implement programs to understand the most commonly used methods with a priority queue

#include <iostream>
#include<queue>
using namespace std; 
  
int main () 
{ 
    priority_queue <int> Prior_q; 
    Prior_q.push(10); 
    Prior_q.push(30); 
    Prior_q.push(6); 
    Prior_q.push(2); 
    Prior_q.push(15);
    Prior_q.push(9);
    Prior_q.push(7);
    
    while (Prior_q.empty() == false) 
    { 
        cout << Prior_q.top() << " "; 
        Prior_q.pop(); 
    } 
  
    return 0; 
}

Output:

30 15 10 9 6 2

In the above program, we used the pop( ), top( ) and push( ) functions which are used most of the times while dealing with a priority queue. Let’s have a look at some of the methods that we can use with a priority queue

size( ): This function Returns the size of the Priority Queue

empty( ): This function is used to check if the priority queue is empty or not. It returns true of the priority queue is empty.

push( ): Inserts an element in the Priority Queue.

pop( ): This function removes the top element of the priority queue which is the element with the highest priority.

swap( ): This function swaps the elements of the priority queue with another priority queue. The function takes a priority queue as a parameter.

emplace( ): This function used to add an element to the top of the priority queue.

Let’s look at one more program.

#include <iostream>
#include<queue>
using namespace std; 
  
int main () 
{ 
    priority_queue <int> Prior_q; 
    Prior_q.push(10); 
    Prior_q.push(30); 
    Prior_q.push(6); 
    Prior_q.push(2); 
    Prior_q.push(15);
    Prior_q.push(9);
    Prior_q.push(7);
    
    while (Prior_q.empty() == false) 
    { 
        cout << Prior_q.top() << " "; 
        Prior_q.pop(); 
    } 
  
    return 0; 
}

Output:

2 6 7 9 10 15 30

With this, we come to an end of this Priority Queue in C++ article. If you wish to learn more, check out the Java Training by Edureka, a trusted online learning company. Edureka’s Java J2EE and SOA training and certification course is designed to train you for both core and advanced Java concepts along with various Java frameworks like Hibernate & Spring.

Got a question for us? Please mention it in the comments section of this blog and we will get back to you as soon as possible.