Ugenz Academy/Tutorial

Priorityqueue

10 min read1,835 words

Reading progress

Keep learning

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

Typetop() returns
Max Priority QueueLargest element
Min Priority QueueSmallest 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.

FeatureQueuePriority Queue
OrderingArrivalPriority
PrincipleFIFOHighest/lowest priority
Main accessFrontHighest/lowest priority
Typical implementationArray/linked list/dequeHeap
pushO(1)O(log n)
RemoveO(1)O(log n)
Get next elementO(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:

OperationComplexity
push()O(log n)
top()O(1)
pop()O(log n)
empty()O(1)
size()O(1)
Build from individual pushesO(n log n)
Build heap bottom-upO(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 27 present?

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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy