Priority Queue Introduction and Concept in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this priority queue code?

Consider the following C++ code using a max priority queue. What will be printed?

DSA C++

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(5);
    pq.push(20);
    pq.push(1);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

A 20 10 5 1

B 1 5 10 20

C 10 20 5 1

D 5 10 1 20

💡 Hint

Remember, a max priority queue always returns the largest element first.

The priority queue stores elements so that the largest is always on top. The output prints elements from largest to smallest.

🧠 Conceptual

intermediate

Which statement about priority queues is true?

Choose the correct statement about priority queues.

A Priority queues always return elements in the order they were inserted.

B Priority queues do not allow duplicate elements.

C Priority queues can only store integers.

D Priority queues return the element with the highest priority first.

💡 Hint

Think about what 'priority' means in a priority queue.

Priority queues return elements based on priority, not insertion order. They can store any data type and allow duplicates.

🔧 Debug

advanced

What error does this priority queue code produce?

Identify the error when compiling this C++ code snippet.

DSA C++

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(20);
    std::cout << pq.pop() << std::endl;
    return 0;
}

A Compilation error: missing semicolon after push

B Compilation error: 'pop' returns void, cannot be used in output

C Runtime error: priority queue is empty

D No error, outputs 20

💡 Hint

Check the return type of the pop() function in priority_queue.

The pop() function removes the top element but returns void. It cannot be used directly in std::cout.

🚀 Application

advanced

How many elements remain after these operations?

Given a min priority queue with elements inserted as 15, 10, 20, 5, then two pop operations are performed. How many elements remain?

DSA C++

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(15);
    pq.push(10);
    pq.push(20);
    pq.push(5);

    pq.pop();
    pq.pop();

    std::cout << pq.size() << std::endl;
    return 0;
}

A 4

B 3

C 2

D 1

💡 Hint

Each pop removes one element from the queue.

Initially 4 elements are inserted. Two pops remove two elements, so 2 remain.

❓ Predict Output

expert

What is the output of this custom priority queue comparator code?

Analyze the output of this C++ code using a priority queue with a custom comparator that prioritizes strings by length (shortest first).

DSA C++

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

struct CompareLength {
    bool operator()(const std::string& a, const std::string& b) {
        return a.length() > b.length();
    }
};

int main() {
    std::priority_queue<std::string, std::vector<std::string>, CompareLength> pq;
    pq.push("apple");
    pq.push("banana");
    pq.push("fig");
    pq.push("date");

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

A fig date apple banana

B banana apple date fig

C apple banana fig date

D date fig banana apple

💡 Hint

The comparator returns true if the first string is longer, so shorter strings have higher priority.

The priority queue orders strings by length ascending. So shortest string 'fig' comes first, then 'date', then 'apple', then 'banana'.

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