Priority Queue Introduction and Concept in DSA C++ - Build from Scratch

Priority Queue Introduction and Concept

📖 Scenario: Imagine you are managing a hospital emergency room. Patients arrive with different levels of urgency. You want to treat the most urgent patients first. This is a perfect use case for a priority queue.

🎯 Goal: You will create a simple priority queue using C++ STL to manage patients by their urgency level. You will add patients with their urgency scores, then retrieve the most urgent patient.

📋 What You'll Learn

Create a priority queue of pairs where each pair contains an integer urgency and a string patient name

Add exactly three patients with given urgency values

Retrieve and print the patient with the highest urgency

💡 Why This Matters

🌍 Real World

Priority queues are used in real life to manage tasks or people by importance, like emergency rooms, task schedulers, or event management.

💼 Career

Understanding priority queues is important for software engineers working on scheduling algorithms, real-time systems, and resource management.

1

Create a priority queue for patients

Include the <queue> and <string> headers. Create a priority queue called patients that stores std::pair<int, std::string> where the integer is urgency and the string is the patient name.

DSA C++

#include 
#include 
#include 

int main() {

    // Create priority queue called patients
    // Your code here

    return 0;
}

Hint

Use std::priority_queue<std::pair<int, std::string>> patients; to create the priority queue.

2

Add patients with urgency levels

Add three patients to the patients priority queue using push: {5, "Alice"}, {2, "Bob"}, and {8, "Charlie"}.

DSA C++

#include 
#include 
#include 

int main() {
    std::priority_queue> patients;

    // Add patients with urgency
    // Your code here

    return 0;
}

Hint

Use patients.push({urgency, "Name"}); to add each patient.

3

Retrieve the most urgent patient

Create a variable top_patient to store the top element of patients using top(). Then remove that patient from the queue using pop().

DSA C++

#include 
#include 
#include 

int main() {
    std::priority_queue> patients;

    patients.push({5, "Alice"});
    patients.push({2, "Bob"});
    patients.push({8, "Charlie"});

    // Get and remove the most urgent patient
    // Your code here

    return 0;
}

Hint

Use patients.top() to get the highest priority patient and patients.pop() to remove it.

4

Print the most urgent patient's name and urgency

Print the most urgent patient's name and urgency in the format: "Most urgent patient: Alice with urgency 5" using top_patient.second for name and top_patient.first for urgency.

DSA C++

#include 
#include 
#include 

int main() {
    std::priority_queue> patients;

    patients.push({5, "Alice"});
    patients.push({2, "Bob"});
    patients.push({8, "Charlie"});

    std::pair top_patient = patients.top();
    patients.pop();

    // Print the most urgent patient
    // Your code here

    return 0;
}

Hint

Use std::cout to print the patient's name and urgency as shown.

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