Priority Queue
A Priority Queue is a data structure where each element has a priority, and the element with the highest priority is processed first.
Unlike a normal queue:
Queue → First In, First Out (FIFO)
A priority queue works according to:
Priority → Highest/Lowest first
The most common implementation is a Heap.
Heap = underlying data structure
Priority Queue = abstract data structure / behavior
1. Normal Queue vs Priority Queue
Normal Queue
Suppose people arrive:
A → B → C → D
They are served:
A → B → C → D
Because it follows:
FIFO
Priority Queue
Suppose:
Person A → Priority 2 Person B → Priority 5 Person C → Priority 1 Person D → Priority 10
The processing order could be:
D → B → A → C
because:
10 > 5 > 2 > 1
The highest-priority element comes first.
2. Real-Life Examples
Priority queues are useful when importance matters more than arrival order.
Emergency Room
Normal patient → Priority 1 Serious patient → Priority 5 Critical patient → Priority 10
The critical patient should be handled first.
CPU Scheduling
Process A → Priority 2 Process B → Priority 8 Process C → Priority 4
The scheduler can process:
B → C → A
Network Traffic
Important packets can be processed before lower-priority packets.
Dijkstra's Algorithm
A priority queue is commonly used to repeatedly select the vertex with the smallest current distance.
3. How Does a Priority Queue Work?
A priority queue can be implemented using several structures:
- Array
- Linked List
- Balanced BST
- Heap ⭐
A heap is usually preferred because it provides efficient insertion and removal.
For example, a Max Heap:
90 / \ 70 80 / \ / \ 40 50 60 30
The highest-priority element is at the root:
90
Therefore:
pq.top();
returns 90.
4. C++ priority_queue
C++ STL provides:
#include <queue>
and:
priority_queue<int> pq;
By default, it behaves as a Max Priority Queue.
5. Max Priority Queue
Example:
#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq; pq.push(30); pq.push(10); pq.push(50); pq.push(20); pq.push(40); cout << pq.top(); return 0; }
Output:
50
Because 50 has the highest value.
6. Main Operations
There are four operations you should remember.
push()
Adds an element.
pq.push(50);
Complexity:
O(log n)
top()
Returns the highest-priority element.
cout << pq.top();
Complexity:
O(1)
Important:
top() does not remove the element.
pop()
Removes the highest-priority element.
pq.pop();
Complexity:
O(log n)
Important:
pop() does not return the removed value.
If you need the value:
int value = pq.top(); pq.pop();
empty()
Checks whether the priority queue is empty.
if (pq.empty()) { cout << "Empty"; }
Complexity:
O(1)
size()
Returns the number of elements.
cout << pq.size();
Complexity:
O(1)
7. Complete Example
#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq; pq.push(30); pq.push(10); pq.push(50); pq.push(20); pq.push(40); cout << "Top: " << pq.top() << endl; pq.pop(); cout << "After pop: " << pq.top() << endl; cout << "Size: " << pq.size() << endl; return 0; }
Output:
Top: 50 After pop: 40 Size: 4
8. Processing All Elements
You can repeatedly use:
while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
For:
30 10 50 20 40
Output:
50 40 30 20 10
Because it is a Max Priority Queue.
⚠️ Remember: this empties the priority queue.
9. Min Priority Queue
Sometimes we want the smallest element first.
For that, use:
priority_queue<int, vector<int>, greater<int>> pq;
Example:
#include <iostream> #include <queue> #include <vector> using namespace std; int main() { priority_queue<int, vector<int>, greater<int>> pq; pq.push(30); pq.push(10); pq.push(50); pq.push(20); pq.push(40); cout << pq.top(); return 0; }
Output:
10
Now:
Smallest = highest priority
10. Processing a Min Priority Queue
while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
Output:
10 20 30 40 50
So a Min Priority Queue can be useful for repeatedly selecting the smallest element.
11. Max vs Min Priority Queue
| Type | top() returns |
|---|---|
| Max Priority Queue | Largest element |
| Min Priority Queue | Smallest element |
C++:
// Max priority_queue<int> pq;
// Min priority_queue<int, vector<int>, greater<int>> pq;
12. Priority Queue With Custom Priority
Priority queues become much more useful when elements contain multiple values.
For example:
Student Name Marks
Suppose we want the student with the highest marks first.
We can use:
priority_queue<pair<int, string>> pq;
Example:
#include <iostream> #include <queue> using namespace std; int main() { priority_queue<pair<int, string>> pq; pq.push({80, "Ram"}); pq.push({95, "Uday"}); pq.push({70, "Hari"}); pq.push({90, "Sita"}); while (!pq.empty()) { cout << pq.top().second << " - " << pq.top().first << endl; pq.pop(); } return 0; }
Output:
Uday - 95 Sita - 90 Ram - 80 Hari - 70
Because the first value of the pair is used for comparison.
13. Custom struct
For more complicated objects, we can create a custom comparator.
Suppose:
struct Student { string name; int marks; };
We want the student with the highest marks first.
struct Compare { bool operator()(Student a, Student b) { return a.marks < b.marks; } };
Then:
priority_queue<Student, vector<Student>, Compare> pq;
Complete example:
#include <iostream> #include <queue> #include <vector> using namespace std; struct Student { string name; int marks; }; struct Compare { bool operator()(Student a, Student b) { return a.marks < b.marks; } }; int main() { priority_queue<Student, vector<Student>, Compare> pq; pq.push({"Ram", 80}); pq.push({"Uday", 95}); pq.push({"Sita", 90}); while (!pq.empty()) { Student s = pq.top(); cout << s.name << " - " << s.marks << endl; pq.pop(); } return 0; }
Output:
Uday - 95 Sita - 90 Ram - 80
14. Min Priority Queue With Custom Objects
Suppose we want the lowest marks first.
Change the comparator:
struct Compare { bool operator()(Student a, Student b) { return a.marks > b.marks; } };
Now:
70 → 80 → 90 → 95
The smallest marks have the highest priority.
15. Priority Queue vs Normal Queue ⭐
This distinction is very important.
Queue
10 → 20 → 30 → 40
Processing:
10 → 20 → 30 → 40
Because:
FIFO
Priority Queue
10 → 20 → 30 → 40
If priority is based on value:
40 → 30 → 20 → 10
Because the highest priority is processed first.
| Feature | Queue | Priority Queue |
|---|---|---|
| Ordering | Arrival | Priority |
| Principle | FIFO | Highest/lowest priority |
| Main access | Front | Highest/lowest priority |
| Typical implementation | Array/linked list/deque | Heap |
push | O(1) | O(log n) |
| Remove | O(1) | O(log n) |
| Get next element | O(1) | O(1) |
16. Priority Queue vs Heap
These terms are related but not identical.
Heap
A data structure.
Example:
Max Heap 90 / \ 70 80
Priority Queue
An abstract data structure describing behavior:
Give me the element with the highest/lowest priority.
A heap is commonly used to implement it.
Think:
Priority Queue | implemented by ↓ Heap
17. Why Not Use a Sorted Array?
Suppose:
[10, 20, 30, 40, 50]
Getting the maximum is easy:
O(1)
But inserting 35 while maintaining sorted order may require shifting elements:
[10,20,30,35,40,50]
which can take:
O(n)
A heap gives:
Insert → O(log n) Get max/min → O(1) Remove max/min → O(log n)
So heaps are usually much better for priority-queue workloads.
18. Priority Queue Applications
1. CPU Scheduling
Processes have priorities:
P1 → 2 P2 → 8 P3 → 5
Processing:
P2 → P3 → P1
2. Dijkstra's Algorithm
A Min Priority Queue can select:
vertex with smallest current distance
This is one of the most important graph applications.
3. Prim's Algorithm
Used to construct a Minimum Spanning Tree.
A priority queue helps select the minimum-weight edge.
4. Huffman Coding
A min priority queue is used to repeatedly select the two nodes with the smallest frequencies.
5. Top K Problems
For example:
Find 10 largest numbers Find 5 smallest numbers Find kth largest element Find kth smallest element
Heaps are extremely common for these.
6. Task Scheduling
Suppose tasks have priorities:
Backup → 1 Security → 10 Update → 5 Emergency → 20
A priority queue processes:
Emergency → Security → Update → Backup
19. Time Complexity
For a heap-based priority queue:
| Operation | Complexity |
|---|---|
push() | O(log n) |
top() | O(1) |
pop() | O(log n) |
empty() | O(1) |
size() | O(1) |
| Build from individual pushes | O(n log n) |
| Build heap bottom-up | O(n) |
20. Important Interview Point
Suppose you have:
[10, 50, 20, 40, 30]
and ask:
What is the largest element?
With a Max Priority Queue:
pq.top()
gives:
50
in:
O(1)
But if you ask:
Is
27present?
A priority queue is not designed for fast arbitrary searching.
You may need:
O(n)
So remember:
Priority Queue → priority access BST → ordered searching
21. The Most Important C++ Syntax
Max Priority Queue
priority_queue<int> pq;
Min Priority Queue
priority_queue<int, vector<int>, greater<int>> pq;
Insert
pq.push(10);
Highest/lowest priority
pq.top();
Remove
pq.pop();
Check empty
pq.empty();
Size
pq.size();
🧠 Final Mental Model
Think of the difference like this:
Queue ↓ "Who came first?" ↓ FIFO Priority Queue ↓ "Who is most important?" ↓ Priority Heap ↓ Common way to efficiently implement Priority Queue
And your DSA progression is now:
Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ⭐ ↓ Trie ↓ Graphs
Remember these 5 points:
1. Priority Queue processes by priority, not arrival order. 2. Max Priority Queue → largest/highest priority first. 3. Min Priority Queue → smallest/highest priority first. 4. Heap is the most common implementation. 5. C++ STL: priority_queue<int> → Max Heap priority_queue<int, vector<int>, greater<int>> → Min Heap