A C++ priority queue is a type of container adapter specifically designed such that first element of the queue is either the greatest or the smallest of all elements in the queue.

What is a Priority Queue?

A priority queue is a data structure that stores element with associated priorities. Unlike a regular queue, where elements are retrieved in a first-in-first-out (FIFO) manner, a priority queue retrieves elements based on their priority. Elements with higher priority are retrieved before those with lower priority, irrespective of the order of insertion.

Syntax

#include <queue>

std::priority_queue<DataType, Container, Compare> pq;

where:

• DataType: Specifies the type of elements to be stored in the priority queue.
• Container: Specifies the underlying container to be used for storage. By default, it is std::vector<DataType>.
• Compare: Specifies the comparison function or functor used to determine the priority order. By default, it is std::less<DataType>, which orders element in decreasing order.

#include <iostream>
#include <queue>

int main() {
    // Declaring a priority queue of integers
    std::priority_queue<int> pq;

    // Pushing elements into the priority queue
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // Accessing the top element
    std::cout << "Top element: " << pq.top() << std::endl;

    // Popping the top element
    pq.pop();

    // Accessing the new top element
    std::cout << "Top element after popping: " << pq.top() << std::endl;

    return 0;
}

// Output
Top element: 30
Top element after popping: 20

// min heap property, the smallest element gets the highest priority.

#include <iostream>
#include <queue>

int main() {
    // Declaring a priority queue of integers with custom comparison function
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;

    // Pushing elements into the priority queue
    minPQ.push(30);
    minPQ.push(10);
    minPQ.push(20);

    // Accessing the top element (smallest element)
    std::cout << "Top element (smallest): " << minPQ.top() << std::endl;

    // Popping the top element
    minPQ.pop();

    // Accessing the new top element (next smallest)
    std::cout << "Top element after popping: " << minPQ.top() << std::endl;

    return 0;
}

// Output
Top element (smallest): 10
Top element after popping: 20

Functions

1 push()

Inserts a new element into the priority queue.

std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);

Complexity: O(log n) - Amortized  constant time, where n is the number of elements in the priority queue. Insertion involves maintaining the heap priority, which takes logarithmic time.

2 top()

Returns a reference to the highest priority element in the priority queue (the one with the maximum value by default).

std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "Top element: " << pq.top() << std::endl; // Output: 30

3 pop()

Removes the highest priority element from the priority queue.

std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.pop();

Complexity: O(log n) - Amortized constant time. Removal involves reordering the heap to maintain the heap property, which takes logarithmic time.

4  size()

Returns the numbers of elements present in the priority queue.

std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "Size of priority queue: " << pq.size() << std::endl; // Output: 3

Complexity: O(1) - Constant time. The size of the priority queue is maintained as a separate variable, so querying it takes constant time.

5 empty()

Checks if the priority queue is empty.

std::priority_queue<int> pq;
std::cout << "Is priority queue empty? " << (pq.empty() ? "Yes" : "No") << std::endl; // Output: Yes

Complexity: O(1) - Constant time. Checking if the priority queue is empty doesn't require any traversal or computation, hence constant time.

Implementation of Priority Queue

Priority queues are commonly implemented using binary heaps due to their efficient insertion, deletion, and retrieval of the maximum (or minimum) element. There are two types of binary heaps: max heaps and min heaps. Max heaps arrange elements such that the parent node is greater than or equal to its children, making the maximum elements accessible in constant time. Min heaps, conversely, arrange elements such that the parent node is less than or equal to its children, allowing for the minimum element to be accessed efficiently.

Binary Heap Structure:

A binary heap is a complete binary tree where each node satisfies the heap property. In a max heap, the value of each node is greater than or equal to the values of its children. In a min heap, the value of each node is less than or equal to the value of its children.

1 Insertion Operation (Push):

When inserting an element into a heap, it is placed at the bottom of the heap (i.e., as a leaf node). Then, the heap property is restored by percolating up the newly inserted element until the heap property is satisfied.

Example:

Let's consider a max heap:

• Initially, we have the following max heap:

         50
       /    \
     30      40
    /  \    /
   20  10  15

We want to insert the element 46 into the heap.

• The element 46 is inserted as a leaf node, place 46 as the left child of 40

         50
       /    \
     30      40
    /  \    /  \
   20  10  15  46

Then, we compare 46 with its parent (40) and swap them if necessary.

• Since 46 > 40, we swap them.

         50
       /    \
     30      46
    /  \    /  \
   20  10  15  40

• Compare 46 with its new parent (50). Since 46 < 50, no further swaps are needed. The heap property is restored.

2 Removal Operation (Pop)

To remove the highest priority element from the heap (i.e., the root node), we follow these steps:

• Remove the root node.
• Replace the root node with the least node to maintain the completeness property of the heap.
• Restore the heap property by percolating down the replacement element until the heap property is satisfied.

Consider a max heap:

         50
       /    \
     46      40
    /  \    /  
   20  10  15

Now, let's remove the root (50)

• Replace 50 with the last leaf node (15)

         15
       /    \
     46      40
    /  \    
   20  10   

• Compare the new root (15) with its children. Swap it with the larger child (46):

         46
       /    \
     15      40
    /  \    
   20  10   

• Heapify down by recursively comparing the swapped node (15) with its children and swapping it with the larger child if necessary:

         46
       /    \
     20      40
    /  \    
   15  10  

Complexity Analysis

Insertion (push): O(log n)

• Insertion involves percolating up the newly inserted element to maintain the heap property, which takes logarithmic time in the worst case.

Accessing the Top Element (top): O(1)

• Accessing the top element is a constant-time operation, as it is always stored at the root of the heap.

Removal (pop()): O(log n)

• Removal involves percolating down the replacement element (the last leaf node) to maintain the heap property, which also takes logarithmic time in the worst case.

Initialize priority using c style array:

#include <iostream>
#include <queue>

int main() {
    int arr[5] = {1, 5, 10, 6, 15};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::priority_queue<int> max_q(arr, arr + n);

    // Now max_q contains all elements from the array, with the maximum at the top

    // Print elements of the priority queue
    std::cout << "Priority Queue elements: ";
    while (!max_q.empty()) {
        std::cout << max_q.top() << " "; // Print the top element
        max_q.pop(); // Remove the top element
    }
    std::cout << std::endl;

    return 0;
}

Initialize priority queue using vector

#include <iostream>
#include <vector>
#include <queue>

int main() {
    std::vector<int> vec = {1, 5, 10, 6, 15};

    // Initialize priority queue with elements from vector
    std::priority_queue<int> max_q(vec.begin(), vec.end());

    // Now max_q contains all elements from the vector, with the maximum at the top

    // Print elements of the priority queue
    std::cout << "Priority Queue elements: ";
    while (!max_q.empty()) {
        std::cout << max_q.top() << " "; // Print the top element
        max_q.pop(); // Remove the top element
    }
    std::cout << std::endl;

    return 0;
}