Priority Queue In C++

In C++, the priority queue represents a specialized container in the STL that focuses solely on the element with the highest priority. While a regular queue adheres to a FIFO (First In First Out) policy, a priority queue removes elements based on their priority, with the highest priority element being dequeued first.

It is similar to the ordinary queue in certain aspects but differs in the following ways:

• ✅ Each element in a priority queue has an associated priority, unlike a regular queue where all elements are treated equally.
• ✅ The element with the highest priority in a priority queue will be removed first, while the queue follows the FIFO(First-In-First-Out) policy means the element that is inserted first will be deleted first.
• ✅ If more than one element exists with the same priority, then the order of the elements in a queue will be taken into consideration.

Syntax

It has the following syntax:

Priority_queue<int>variable_name;

In this particular syntax,

• ✅ int denotes the data type of the element.
• ✅ variable_name represents the identifier of the variable.

Priority queue container provides a pre-built implementation of the binary heap data structure. There are typically two variations of heaps that can be utilized.

1) Max Heap Priority Queue (by default)

In a Max Heap priority queue, the item with the greatest value is given the highest priority and is retrieved first. This is the default functionality of std::priority_queue in the C++ programming language.

Syntax

It has the following syntax:

std::priority_queue<data_type> maxHeap;

In this particular notation,

• ✅ data_type signifies the type of elements that are stored within the priority queue.

Max Heap Priority Queue Example

Let's consider a straightforward example to demonstrate the implementation of a max heap priority queue in C++.

Example

#include <iostream>

#include <queue>

int main() {

    std::priority_queue<int> maxHeap;

    maxHeap.push(10);

    maxHeap.push(30);

    maxHeap.push(20);

    maxHeap.push(5);

    std::cout << "Elements in max-heap order: ";

    while (!maxHeap.empty()) {

        std::cout << maxHeap.top() << " ";

        maxHeap.pop();

    }

    return 0;

}

Output:

Elements in max-heap order: 30 20 10 5

Explanation

In this instance, the priority_queue<int> is implemented with std::less<int> as its default comparator. The element with the highest value (30) is assigned the topmost priority, leading to elements being displayed in a descending order based on their values.

2) Min Heap Priority Queue (Custom Comparator)

In a priority queue implemented as a Min Heap, the element with the smallest value is considered to have the highest priority and is retrieved first. This behavior can be accomplished by employing a user-defined comparator such as std::greater.

Syntax

It has the following syntax:

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

In this syntax,

• ✅ Vector<int>: It represents the STL Container.
• ✅ greater<int>: It represents the comparator class.

Min Heap Priority Queue Example

Let's consider a scenario to demonstrate the minimum heap within the priority queue in C++.

Example

#include <iostream>

#include <queue>

#include <vector>

#include <functional>

int main() {

    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(10);

    minHeap.push(30);

    minHeap.push(20);

    minHeap.push(5);

    std::cout << "Elements in min-heap order: ";

    while (!minHeap.empty()) {

        std::cout << minHeap.top() << " ";

        minHeap.pop();

    }

    return 0;

}

Output:

Elements in min-heap order: 5 10 20 30

Explanation

The third parameter in the template, std::greater<int>, alters the functionality to form a min-heap. The element with the smallest value (5) is given the topmost priority. The elements are displayed in ascending order based on their values.

Let's explore the concept of priority queues using a basic illustration.

In the preceding diagram, elements were added using the push method, and the process of inserting is the same as a standard queue. However, during deletion with the pop method, the element with the topmost priority will be removed initially.

Basic Operations of Priority Queues

Various fundamental functions of priority queues in C++ include:

1) Inserting Elements

In priority queues, the add function is employed to add elements to the queue. The heap condition remains unchanged with each addition as it automatically places the highest priority item (usually the greatest) at the top.

2) Accessing Top Element

The top method retrieves the highest element in the priority queue, which is determined by its default highest priority value. This data structure enables quick access to the maximum element with a time complexity of O(1) without removing it. By using the top function, we can observe the maximum value before proceeding with operations like pop.

Inserting and Accessing Top Element Example

Let's consider a scenario to demonstrate the process of inserting and retrieving elements in a priority queue.

Example

#include <iostream>

#include <queue>

using namespace std;

int main() {

    priority_queue<int> pq;

    pq.push(70);

    pq.push(60);

    pq.push(90);

    pq.push(55);

    cout << "Maximum element: " << pq.top() << endl;

    return 0;

}

Output:

Maximum element: 90

Explanation

In this instance, the priority queue is populated with the elements 70, 60, 90, and 55 sequentially. When organized as a max-heap, the element 90 naturally becomes the highest priority. Utilizing pq.top accurately yields the value 90, showcasing the queue's adherence to prioritizing elements during its functions.

3) Deleting Top Element

The pop method is employed to remove the element positioned at the front (top element) of a priority queue according to its priority level. It is recommended for users to utilize the top method initially to fetch the eliminated element since pop does not provide any return value. Subsequently, the queue system proceeds to process the subsequent largest element, which seamlessly transitions into the topmost position.

Deletion of Top Element in Priority Queue Example

Let's consider an illustration to demonstrate the process of removing the highest-priority item from the priority queue.

Example

#include <iostream>

#include <queue>

using namespace std;

int main() {

    priority_queue<int> pq;

    pq.push(15);

    pq.push(35);

    pq.push(25);

    cout << "Before pop, top: " << pq.top() << endl;

    pq.pop();

    cout << "After pop, new top: " << pq.top() << endl;

    return 0;

}

Output:

Before pop, top: 35

After pop, new top: 25

Explanation

The priorityqueue is populated with the values 15, 35, and 25. Among these elements, 35 holds the highest priority in the priorityqueue because of its size compared to others prior to executing the pop function. Once pop is executed, 35 is taken out of the queue, resulting in 25 taking over as the element with the highest priority.

4) Traversing (Pseudo Traversal)

A priority queue doesn't offer direct traversal like vectors or lists. To access all elements, you start with top and then perform a pop immediately. The elements are printed out in descending order due to the priority queue's default max-heap structure.

C++ Traversing Example in Priority Queue

Let's consider an illustration to demonstrate navigating through the priority queue in C++.

Example

#include <iostream>

#include <queue>

using namespace std;

int main() {

    priority_queue<int> pq;

    pq.push(20);

    pq.push(10);

    pq.push(30);

    cout << "Elements in descending order: ";

    while (!pq.empty()) {

        cout << pq.top() << " ";

        pq.pop();

    }

    cout << endl;

    return 0;

}

Output:

Elements in descending order: 30 20 10

Explanation

In this instance, the numbers 20, 10, and 30 are added. Subsequently, the highest position in the priority queue contains the largest value due to its specific queue structure. The process then proceeds with 20 as the next largest value, followed by the printing of 10. The order of printing maintains a descending pattern for all the inserted elements.

5) Changing Priority Queue Order

C++ programmers have the ability to modify the order of a priority queue within their software by defining a custom comparator. The standard behavior of a C++ priority queue is to operate as a max-heap, where elements with higher priority are placed at the top of the structure. By using a custom comparator, developers can change the default max-heap configuration to a min-heap or implement a personalized prioritization system.

Example of Changing the Priority Queue Order

Let's consider an example to demonstrate how to modify the order of elements in a priority queue using C++.

Example

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

int main() {

    // Custom comparator for a min-heap (using greater<int>)

    priority_queue<int, vector<int>, greater<int>> minHeap;

    minHeap.push(40);

    minHeap.push(10);

    minHeap.push(30);

    cout << "Top element (min-heap): " << minHeap.top() << endl; // Output: 10

    return 0;

}

Output:

Top element (min-heap): 10

Explanation

The application of the greater<int> method converts standard max-heaps into min-heaps within the software. The highest position in a min-heap holds the smallest element among all. When the queue is processed, the result reflects 10 as it signifies the minimum element saved in the priority queue.

Time Complexity

Member Function of Priority Queue

Various member methods of priority queues in C++ include:

C++ Priority Queue Example

Let's explore a different instance of a priority queue in C++.

Example

#include <iostream>  

#include<queue>  

using namespace std;  

int main()  

{  

   priority_queue<int> p;  // priority queue declaration  

   priority_queue<int> q;  // priority queue declaration  

   p.push(1); // inserting element '1' in p.  

   p.push(2); // inserting element '2' in p.  

   p.push(3); // inserting element '3' in p.  

   p.push(4); // inserting element '4' in p.  

   q.push(5); // inserting element '5' in q.  

   q.push(6); // inserting element '6' in q.  

   q.push(7); // inserting element '7' in q.  

   q.push(8); // inserting element '8' in q.  

   p.swap(q);  

   cout << "Elements of p are: " << endl;  

   while(!p.empty())  

   {  

      cout << p.top() << endl;  

       p.pop();  

   }  

   cout << "Elements of q are:" << endl;  

    while(!q.empty())  

   {  

      cout << q.top() << endl;  

       q.pop();  

   }  

    return 0;  

}

Output:

Elements of p are :

8

7

6

5

Elements of q are :

4

3

2

1

Explanation

In the provided code snippet, we defined two priority queues named 'p' and 'q'. Four elements were added to the 'p' priority queue, and another four elements were added to the 'q' priority queue. Following the insertion of elements, a function called swap was employed to exchange the elements between the 'p' and 'q' queues.

Purpose of the Priority Queues

Several purposes of the priority queues in C++ are as follows:

• ✅ Efficient Element Access: Priority queues enable constant-time (O(1)) element lookup of the most prioritized item and logarithmic (O(log n)) operations on insert and delete commands. Therefore, they excel at high-performance applications.
• ✅ Order Management: The system performs automatic element realignment through reordering processes to keep priority intact after adding or removing entries.
• ✅ Support for Custom Priorities: The priority queue system allows users to create their element comparison methods through custom comparator tools.
• ✅ Useful in Real-time Processing: Real-time processing systems receive maximum benefit from using priority queues because they enable quick responses to high-priority tasks.

Conclusion

In summary, C++ priority queues offer developers efficient access to either the highest or lowest priority elements. By leveraging an STL priority queue, developers can construct heaps for scheduling tasks, searching systems, and managing resource allocation operations. The time complexity for adding and removing data in priority queues is O(log n), making them well-suited for applications that require high performance.

C++ Priority Queue MCQs

1) What is the default behaviour of a priority_queue in C++?

• ✅ Returns the element with the lowest priority first
• ✅ Stores elements in insertion order
• ✅ Returns the element with the highest priority first
• ✅ Returns the element with the most recent addition first

Returns the element of highest priority as the answer.

2) How can we change the default behaviour of a C++ priority_queue to access the smallest element first?

• ✅ By using a stack instead
• ✅ The implementation requires a Custom comparator.
• ✅ The container requires manual sorting following each new insertion.
• ✅ It is not possible.

3) How does a priority queue differ conceptually from a standard queue?

• ✅ A priority queue maintains its elements inside a circular buffer structure.
• ✅ A priority queue needs linked lists for its implementation.
• ✅ The priority queue system eliminates elements that have low priority status.
• ✅ A priority queue determines the sequence of element processing through priority rankings instead of arrival order.

4) Why are priority queues important in algorithm design?

• ✅ The system uses priority queues for effective task management of priority-based items
• ✅ They simplify pointer manipulation
• ✅ Priority queues serve essential roles in recursive systems.
• ✅ Priority queues enable random data storage through their mechanisms.

a) The system utilizes priority queues to efficiently manage tasks based on their priority levels.

5) What is the main purpose of the comparator in a priority queue?

• ✅ Researchers determine queue storage capacity as the first objective.
• ✅ The second function enables post-insertion element sorting.
• ✅ The mechanism helps decide which elements receive priority first.
• ✅ The third requirement establishes how to specify the container type.

c) This process aids in determining the order in which elements are given precedence.