Priority Queue Introduction and Concept in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Priority Queue?

A Priority Queue is a special type of queue where each element has a priority. Elements with higher priority are served before elements with lower priority, unlike a normal queue which follows first-in-first-out order.

beginner

How does a Priority Queue differ from a regular Queue?

In a regular queue, elements are processed in the order they arrive (FIFO). In a Priority Queue, elements are processed based on their priority, not just arrival time.

beginner

What are the common operations of a Priority Queue?

Common operations include:
1. Insert (add an element with priority)
2. Extract (remove the element with highest priority)
3. Peek (view the element with highest priority without removing it)

intermediate

Which data structure is commonly used to implement a Priority Queue efficiently?

A Priority Queue is often implemented using a Heap data structure, especially a Binary Heap, because it allows fast insertion and extraction of the highest priority element.

beginner

What real-life example can help understand Priority Queues?

Think of a hospital emergency room where patients are treated based on the severity of their condition (priority), not just the order they arrived.

What determines the order of elements in a Priority Queue?

A The priority of elements

B The order elements were added

C The size of elements

D The alphabetical order of elements

Priority Queues order elements based on their priority, not the order they were added.

Which operation removes the highest priority element from a Priority Queue?

A Peek

B Insert

C Extract

D Sort

Extract removes the element with the highest priority from the Priority Queue.

Which data structure is commonly used to implement a Priority Queue efficiently?

A Array

B Heap

C Stack

D Linked List

Heaps, especially binary heaps, are used to implement Priority Queues efficiently.

In a Priority Queue, if two elements have the same priority, what usually decides which one is served first?

A The element that arrived first

B Random choice

C The element with smaller value

D The element with larger value

Usually, if priorities are equal, the element that arrived first is served first (stable priority queue).

Which of these is NOT a typical operation of a Priority Queue?

A Insert

B Extract

C Peek

D Reverse

Reverse is not a typical operation of a Priority Queue.

Explain what a Priority Queue is and how it works.

Think about how elements are chosen to be removed.

Describe common operations of a Priority Queue and a data structure used to implement it.

Consider how to add, remove, and view elements efficiently.

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