Priority Queue Introduction and Concept in DSA C++

Mental Model

A priority queue is like a line where people with higher importance get served first, no matter when they arrive.

Analogy: Imagine a hospital emergency room where patients with more serious conditions are treated before others, even if they arrived later.

Priority Queue:
[ 5 ] -> [ 3 ] -> [ 4 ] -> [ 1 ] -> null
↑ front (highest priority)

Dry Run Walkthrough

Input: Insert values 3, 5, 1, 4 into an empty priority queue (higher number means higher priority).

Goal: To insert elements so that the highest priority element is always at the front.

Step 1: Insert 3 into empty queue

[3] -> null ↑ front

Why: First element becomes the front as it is the only one.

Step 2: Insert 5, which has higher priority than 3

[5] -> [3] -> null ↑ front

Why: 5 moves to front because it has higher priority than 3.

Step 3: Insert 1, which has lower priority than 3

[5] -> [3] -> [1] -> null ↑ front

Why: 1 goes to the end because it has lowest priority.

Step 4: Insert 4, which fits between 5 and 3

[5] -> [4] -> [3] -> [1] -> null ↑ front

Why: 4 is placed after 5 but before 3 to keep order by priority.

Result:

[5] -> [4] -> [3] -> [1] -> null ↑ front

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class PriorityQueue {
private:
    Node* front;
public:
    PriorityQueue() : front(nullptr) {}

    void insert(int val) {
        Node* newNode = new Node(val);
        if (!front || val > front->data) {
            newNode->next = front;  // place newNode before front
            front = newNode;        // update front
            return;
        }
        Node* curr = front;
        while (curr->next && curr->next->data > val) {
            curr = curr->next;    // move forward to find correct spot
        }
        newNode->next = curr->next; // insert newNode after curr
        curr->next = newNode;
    }

    void print() {
        Node* curr = front;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

int main() {
    PriorityQueue pq;
    pq.insert(3);
    pq.insert(5);
    pq.insert(1);
    pq.insert(4);
    pq.print();
    return 0;
}

if (!front || val > front->data) {

Check if new value has higher priority than front or queue is empty

newNode->next = front; // place newNode before front front = newNode; // update front

Insert new node at front to keep highest priority first

while (curr->next && curr->next->data > val) { curr = curr->next; // move forward to find correct spot }

Traverse to find the right position to insert new node by priority

newNode->next = curr->next; // insert newNode after curr curr->next = newNode;

Insert new node in the correct position to maintain order

Output

5 -> 4 -> 3 -> 1 -> null

Complexity Analysis

Time: O(n) because in worst case we may traverse all nodes to insert in correct position

Space: O(n) because each inserted element creates a new node in the queue

vs Alternative: Compared to a simple queue where insertion is O(1) at end, priority queue insertion is slower due to ordering but allows quick access to highest priority element

Edge Cases

Empty queue

New element becomes front directly

DSA C++

if (!front || val > front->data) {

Insert element with highest priority

Inserted at front

DSA C++

if (!front || val > front->data) {

Insert element with lowest priority

Inserted at the end after traversing all nodes

DSA C++

while (curr->next && curr->next->data > val) {

When to Use This Pattern

When you need to always process the highest priority item first, use a priority queue because it keeps elements ordered by importance automatically.

Common Mistakes

Mistake: Inserting new elements only at the end without ordering
Fix: Traverse to find correct position and insert to maintain priority order

Mistake: Not updating front pointer when new highest priority element arrives
Fix: Check if new element has higher priority than front and update front accordingly

Summary

A priority queue stores elements so that the highest priority is always accessed first.

Use it when you need to process items by importance, not just arrival order.

The key is to insert elements in order so the front always holds the highest priority.

Practice

1. What is the main property of a priority queue in data structures?

easy

A. Elements are always served in the order they were inserted

B. Elements are served based on their priority, not just insertion order

C. It stores elements in sorted order permanently

D. It only allows insertion of unique elements

Solution

1. Step 1: Understand priority queue behavior

   A priority queue serves elements based on priority, not just the order they arrive. Options A, C, and D describe other data structures or incorrect properties.

2. Final Answer:

   Elements are served based on their priority, not just insertion order -> Option B

3. Quick Check:

   Priority queue = priority-based serving [OK]

Hint: Remember: priority queue serves highest priority first [OK]

Common Mistakes:

• Confusing priority queue with regular queue
• Thinking elements are always sorted inside
• Assuming only unique elements allowed

2. Which of the following is the correct way to declare a max priority queue of integers in C++ STL?

easy

A. std::priority_queue<int> pq;

B. std::priority_queue pq;

C. std::priority_queue pq;

D. std::priority_queue pq;

Solution

1. Step 1: Recall default priority queue type

   By default, std::priority_queue is a max heap using std::vector and std::less. std::priority_queue<int> pq; uses default syntax. B creates min priority queue. C and D use invalid container type std::list.

2. Final Answer:

   std::priority_queue<int> pq; -> Option A

3. Quick Check:

   Default priority queue is max heap [OK]

Hint: Default priority_queue<int> is max heap in C++ STL [OK]

Common Mistakes:

• Using std::greater<int> for max heap (it's for min heap)
• Using unsupported container types like std::list
• Overcomplicating declaration when default works

3. What will be the output of the following C++ code snippet?

std::priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(20);
std::cout << pq.top() << std::endl;
pq.pop();
std::cout << pq.top() << std::endl;

medium

A. 20\n10

B. 10\n5

C. 5\n10

D. 20\n5

Solution

1. Step 1: Insert elements into max priority queue

   Elements 10, 5, 20 pushed; max 20 at top, print 20. After pop, 20 removed, next max 10, print 10.

2. Final Answer:

   20\n10 -> Option A

3. Quick Check:

   Max heap top changes from 20 to 10 after pop [OK]

Hint: Top always shows current max in max priority queue [OK]

Common Mistakes:

• Confusing priority queue with FIFO queue
• Assuming pop removes smallest element
• Mixing up order of outputs

4. Identify the error in the following C++ code using priority queue:

std::priority_queue<int> pq;
pq.push(15);
pq.push(30);
pq.pop();
std::cout << pq.top() << std::endl;
pq.pop();
pq.pop();

medium

A. Missing semicolon after pq.push(30)

B. Using std::cout without including <iostream>

C. Calling pop() on empty priority queue causes runtime error

D. Priority queue cannot store integers

Solution

1. Step 1: Trace push and pop operations

   Push 15, 30; first pop removes 30, top now 15 printed; second pop removes 15; third pop on empty queue causes runtime error.

2. Final Answer:

   Calling pop() on empty priority queue causes runtime error -> Option C

3. Quick Check:

   Pop on empty queue = error [OK]

Hint: Never pop from empty priority queue [OK]

Common Mistakes:

• Ignoring empty check before pop
• Assuming pop returns value
• Confusing syntax errors with runtime errors

5. You want to maintain a priority queue that always gives the smallest element first (a min priority queue). Which of the following is the correct way to declare it in C++ STL?

hard

A. std::priority_queue pq;

B. std::priority_queue<int> pq;

C. std::priority_queue pq;

D. std::priority_queue pq;

Solution

1. Step 1: Understand default and min heap declaration

   Default std::priority_queue is max heap (std::less). For min heap (smallest first), use std::greater with std::vector. A and B are max heaps; D uses unsupported std::list.

2. Final Answer:

   std::priority_queue<int, std::vector<int>, std::greater<int>> pq; -> Option D

3. Quick Check:

   Min heap = priority_queue with std::greater [OK]

Hint: Use std::greater for min priority queue in C++ STL [OK]

Common Mistakes:

• Using std::less for min heap
• Using unsupported containers like std::list
• Forgetting to specify comparator