Priority Queue In Data Structures | Types, Uses & More (+Examples)

0 min read

Imagine you're in a hospital emergency room — patients aren’t treated based on when they arrive, but on how critical their condition is. That’s the idea behind a priority queue. Unlike a regular queue that simply follows the First-In-First-Out (FIFO) rule, a priority queue organizes elements based on their importance. Higher-priority elements are handled before lower-priority ones, no matter when they entered the system.

In this article, we’ll break down the concept of priority queues, explore how they’re implemented, walk through real-world examples, and understand why they play a vital role in designing efficient algorithms and systems.

What Is A Priority Queue?

A priority queue is an abstract data type in which each element is associated with a priority. Unlike a regular queue that operates in a First-In-First-Out (FIFO) manner, a priority queue processes elements based on their priority — not their order of insertion. The element with the highest priority is always removed first.

In essence, a priority queue allows for selective processing of elements based on their importance.

Key Properties Of A Priority Queue:

1. Each element has a priority: Every item inserted into a priority queue is assigned a priority value. This value determines the order in which elements are processed.
2. Higher-priority elements are served before lower-priority ones: When an element is removed (or dequeued) from the queue, it’s always the one with the highest priority, regardless of when it was inserted.

How Priority Affects The Order Of Processing:

Consider the following elements with their associated priorities:

If lower numbers represent higher priority, the order in which these tasks will be processed is:

Task B → Task C → Task A

Even though Task A might have been inserted first, it is processed last because it has the lowest priority.

This illustrates a fundamental difference from regular queues: in a priority queue, the order of processing depends entirely on priority values, not on insertion order.

Also Read About: Circular Queue In Data Structures | Working & More (+Examples)

How Does A Priority Queue Differ From Other Queues?

At first glance, queues may all seem alike — they store elements and allow insertion and removal. However, the rules that govern insertion and removal vary significantly across different types of queues.

The priority queue in data structures stands out because it organizes elements not by the order they arrive but by the priority assigned to them. This makes it fundamentally different from structures like regular queues and stacks.

Let’s take a look at how each structure works:

• A regular queue follows the First-In-First-Out (FIFO) principle. The element inserted first is removed first.
• A stack follows the Last-In-First-Out (LIFO) principle. The most recently added element is removed first.
• A priority queue removes the element with the highest priority, regardless of when it was inserted.

Comparison Table: Priority Queue Vs Other Queues

In summary, the priority queue is more adaptive and intelligent in processing elements by assigning and acting upon priorities, making it ideal for scenarios where importance matters more than timing.

Types Of Priority Queues In Data Structures

A priority queue doesn't just come in one flavor — there are different types depending on how the priority is defined and how elements are processed. Let's explore the key variations:

1. Ascending Priority Queue

• Definition: In this type, lower values indicate higher priority.
• Behavior: The smallest element (in terms of value) is served first.
• Use Case: Task schedulers that prioritize urgent or lightweight tasks (e.g., shortest-job-first algorithms).

Example: If you insert elements 7, 2, 5 into an ascending priority queue, they will be processed in this order:

2 → 5 → 7

2. Descending Priority Queue

• Definition: Here, higher values indicate higher priority.
• Behavior: The largest element is processed first.
• Use Case: Applications where larger values represent urgency or importance (e.g., military threat levels, emergency signals).

Example: For elements 7, 2, 5, a descending priority queue would process them as:

7 → 5 → 2

3. Double-Ended Priority Queue (DEPQ)

• Definition: A DEPQ allows for the removal of both the highest and lowest priority elements.
• Behavior: Supports two operations — removeMin() and removeMax().
• Use Case: Resource allocation systems where both ends (least and most demanding) need to be handled efficiently.

Implementation Of Priority Queue

A priority queue can be implemented in multiple ways, and the choice of implementation directly impacts performance. Below are the most common methods:

1. Using Arrays or Linked Lists (Basic Implementation)

a. Unsorted Array / Linked List

• Insertion: O(1) — Simply append the element at the end.
• Deletion (of highest priority): O(n) — Need to search the entire structure for the highest-priority element.

b. Sorted Array / Linked List

• Insertion: O(n) — Insert in the correct position to maintain sorting.
• Deletion: O(1) — The highest-priority element is always at one end.

When to use: Good for small datasets or where insertion frequency is low and deletion needs to be fast (or vice versa).

Code Example:

            #include 
#include 
using namespace std;

class PriorityQueue {
    vector<pair<int, int>> queue; // {value, priority}
public:
    void insert(int value, int priority) {
        queue.push_back({value, priority});
    }

    int extractMax() {
        if (queue.empty()) return -1;
        int maxIndex = 0;
        for (int i = 1; i < queue.size(); i++) {
            if (queue[i].second > queue[maxIndex].second)
                maxIndex = i;
        }
        int result = queue[maxIndex].first;
        queue.erase(queue.begin() + maxIndex);
        return result;
    }
};

int main() {
    PriorityQueue pq;
    pq.insert(10, 1);
    pq.insert(20, 3);
    pq.insert(30, 2);

    cout << "Removed: " << pq.extractMax() << endl; // 20
    cout << "Removed: " << pq.extractMax() << endl; // 30
    return 0;
}

          

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgUHJpb3JpdHlRdWV1ZSB7CiAgICB2ZWN0b3I8cGFpcjxpbnQsIGludD4+IHF1ZXVlOyAvLyB7dmFsdWUsIHByaW9yaXR5fQpwdWJsaWM6CiAgICB2b2lkIGluc2VydChpbnQgdmFsdWUsIGludCBwcmlvcml0eSkgewogICAgICAgIHF1ZXVlLnB1c2hfYmFjayh7dmFsdWUsIHByaW9yaXR5fSk7CiAgICB9CgogICAgaW50IGV4dHJhY3RNYXgoKSB7CiAgICAgICAgaWYgKHF1ZXVlLmVtcHR5KCkpIHJldHVybiAtMTsKICAgICAgICBpbnQgbWF4SW5kZXggPSAwOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgcXVldWUuc2l6ZSgpOyBpKyspIHsKICAgICAgICAgICAgaWYgKHF1ZXVlW2ldLnNlY29uZCA+IHF1ZXVlW21heEluZGV4XS5zZWNvbmQpCiAgICAgICAgICAgICAgICBtYXhJbmRleCA9IGk7CiAgICAgICAgfQogICAgICAgIGludCByZXN1bHQgPSBxdWV1ZVttYXhJbmRleF0uZmlyc3Q7CiAgICAgICAgcXVldWUuZXJhc2UocXVldWUuYmVnaW4oKSArIG1heEluZGV4KTsKICAgICAgICByZXR1cm4gcmVzdWx0OwogICAgfQp9OwoKaW50IG1haW4oKSB7CiAgICBQcmlvcml0eVF1ZXVlIHBxOwogICAgcHEuaW5zZXJ0KDEwLCAxKTsKICAgIHBxLmluc2VydCgyMCwgMyk7CiAgICBwcS5pbnNlcnQoMzAsIDIpOwoKICAgIGNvdXQgPDwgIlJlbW92ZWQ6ICIgPDwgcHEuZXh0cmFjdE1heCgpIDw8IGVuZGw7IC8vIDIwCiAgICBjb3V0IDw8ICJSZW1vdmVkOiAiIDw8IHBxLmV4dHJhY3RNYXgoKSA8PCBlbmRsOyAvLyAzMAogICAgcmV0dXJuIDA7Cn0K

Output:

Removed: 20
Removed: 30

Explanation:

In the above code example-

1. We use #include directives to import the necessary libraries like <iostream> and <vector> for input-output and dynamic array functionalities.
2. Next, we define a PriorityQueue class that holds a vector<pair<int, int>> to store pairs representing the value and its priority.
3. We then implement the insert() method, which inserts a new value with its priority into the queue using queue.push_back().
4. We also implement the extractMax() method, which extracts the value with the highest priority from the queue. It searches for the highest priority by iterating through the queue, finds the maximum, and removes it. If the queue is empty, it returns -1.
5. In the main() function, we create a PriorityQueue object and insert three values with different priorities: (10, 1), (20, 3), and (30, 2).
6. Finally, we call extractMax() twice to remove the values with the highest priority first, printing 20 and 30 as the result.

2. Using Binary Heap (Optimal and Widely Used)

A Binary Heap is a complete binary tree used to efficiently implement priority queues. Two types:

• Min Heap: Root holds the minimum value (for ascending priority queues).
• Max Heap: Root holds the maximum value (for descending priority queues).

Time Complexities:

• Insertion: O(log n)
• Deletion (extract max/min): O(log n)
• Peek (view top element): O(1)

Why preferred: Efficient, balanced performance. Used in real-world systems like task schedulers, Dijkstra’s algorithm, etc.

Code Example:

            #include 
#include 
using namespace std;

int main() {
    priority_queue pq; // Max-heap

    pq.push(10);
    pq.push(20);
    pq.push(30);

    cout << "Top: " << pq.top() << endl; // 30
    pq.pop();
    cout << "Top: " << pq.top() << endl; // 20
    return 0;
}

          

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKICAgIHByaW9yaXR5X3F1ZXVlPGludD4gcHE7IC8vIE1heC1oZWFwCgogICAgcHEucHVzaCgxMCk7CiAgICBwcS5wdXNoKDIwKTsKICAgIHBxLnB1c2goMzApOwoKICAgIGNvdXQgPDwgIlRvcDogIiA8PCBwcS50b3AoKSA8PCBlbmRsOyAvLyAzMAogICAgcHEucG9wKCk7CiAgICBjb3V0IDw8ICJUb3A6ICIgPDwgcHEudG9wKCkgPDwgZW5kbDsgLy8gMjAKICAgIHJldHVybiAwOwp9Cg==

Output:

Top: 30
Top: 20

Explanation:

In the above code example-

1. We use #include directives to import the necessary libraries like <iostream> and <queue> for input-output and queue operations.
2. Then, we use priority_queue<int> to create a max-heap priority queue that stores integer values.
3. Next, we insert three integers into the queue: 10, 20, and 30 using pq.push().
4. We also use pq.top() to check the top value of the queue, which is 30, since it's the highest value in the max-heap.
5. Finally, we remove the top element using pq.pop(). After that, we use pq.top() again to print the new top value, which is 20.

3. Using Balanced Trees (e.g., Red-Black Trees, AVL Trees)

These are self-balancing binary search trees that maintain sorted order while allowing fast insertions and deletions.

Time Complexities:

• Insertion: O(log n)
• Deletion: O(log n)
• Search/Peek: O(log n)

Benefits:

• Allows range queries (e.g., find all elements with priority between 10 and 20).
• Supports double-ended priority queue operations efficiently.

When to use: When both order and fast lookup are important, especially in complex algorithms or systems requiring ordered data traversal.

Code Example:

            #include 
#include 
using namespace std;

int main() {
    // Pair = {priority, value}
    set<pair<int, int>> pq;

    pq.insert({1, 10});
    pq.insert({3, 20});
    pq.insert({2, 30});

    // Remove highest priority (largest priority)
    auto it = --pq.end();
    cout << "Removed: " << it->second << endl; // 20
    pq.erase(it);

    // Remove lowest priority
    it = pq.begin();
    cout << "Removed: " << it->second << endl; // 10
    return 0;
}

          

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CiAgICAvLyBQYWlyID0ge3ByaW9yaXR5LCB2YWx1ZX0KICAgIHNldDxwYWlyPGludCwgaW50Pj4gcHE7CgogICAgcHEuaW5zZXJ0KHsxLCAxMH0pOwogICAgcHEuaW5zZXJ0KHszLCAyMH0pOwogICAgcHEuaW5zZXJ0KHsyLCAzMH0pOwoKICAgIC8vIFJlbW92ZSBoaWdoZXN0IHByaW9yaXR5IChsYXJnZXN0IHByaW9yaXR5KQogICAgYXV0byBpdCA9IC0tcHEuZW5kKCk7CiAgICBjb3V0IDw8ICJSZW1vdmVkOiAiIDw8IGl0LT5zZWNvbmQgPDwgZW5kbDsgLy8gMjAKICAgIHBxLmVyYXNlKGl0KTsKCiAgICAvLyBSZW1vdmUgbG93ZXN0IHByaW9yaXR5CiAgICBpdCA9IHBxLmJlZ2luKCk7CiAgICBjb3V0IDw8ICJSZW1vdmVkOiAiIDw8IGl0LT5zZWNvbmQgPDwgZW5kbDsgLy8gMTAKICAgIHJldHVybiAwOwp9Cg==

Output:

Removed: 20
Removed: 10

Explanation:

In the above code example-

1. We use #include directives to import the necessary libraries like <iostream> and <set> for input-output and set operations.
2. Then, we use set<pair<int, int>> to create a set where each element is a pair of integers representing priority and value.
3. Next, we insert three pairs into the set: (1, 10), (3, 20), and (2, 30).
4. We use auto it = --pq.end() to get an iterator pointing to the largest priority (highest value) and print the second element of the pair, which is 20.
5. Then, we use pq.erase(it) to remove the element with the highest priority.
6. Next, we use auto it = pq.begin() to get an iterator pointing to the smallest priority (lowest value) and print the second element of the pair, which is 10.
7. Finally, we remove the element with the lowest priority using pq.erase(it).

When to Prefer Which Implementation?

Why It Matters: It combines the flexibility of both ascending and descending types and is useful when you need dual-priority access in dynamic scenarios.

Operations On Priority Queues

Some of the most commonly used operations on priority queues are as follows:

1. Insertion (Enqueue)

• Add an element with its associated priority.
• Where the element is placed depends on the underlying data structure.

2. Deletion (Dequeue / Remove Highest Priority)

• Remove the element with the highest priority (e.g., the root of a heap, or the last in a sorted list).
• This is the core operation of a priority queue.

3. Peek (Get Highest Priority)

• View (but don’t remove) the element with the highest priority.
• Typically O(1) in most implementations like heaps.

4. Update Priority

• Change the priority of an existing element.
• Not always supported directly in standard libraries — may require re-insertion or custom handling.

Time Complexity Comparison

In a binary heap, updating priority typically requires re-insertion (i.e., remove + insert).

Code Example:

            #include 
#include 
#include 

using namespace std;

int main() {
    // Max-Heap priority queue
    priority_queue<pair<int, string>> pq;

    // Insertion
    pq.push({3, "Task A"});
    pq.push({5, "Task B"});
    pq.push({1, "Task C"});

    // Peek
    cout << "Top Priority: " << pq.top().second << " (Priority " << pq.top().first << ")\n";

    // Deletion
    pq.pop(); // removes "Task B"

    // Peek after deletion
    cout << "Next Top Priority: " << pq.top().second << " (Priority " << pq.top().first << ")\n";

    // Update Priority: Reinsert "Task C" with new higher priority
    pq.push({6, "Task C (Updated)"});

    // Peek again
    cout << "After Updating: " << pq.top().second << " (Priority " << pq.top().first << ")\n";

    return 0;
}

          

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CiAgICAvLyBNYXgtSGVhcCBwcmlvcml0eSBxdWV1ZQogICAgcHJpb3JpdHlfcXVldWU8cGFpcjxpbnQsIHN0cmluZz4+IHBxOwoKICAgIC8vIEluc2VydGlvbgogICAgcHEucHVzaCh7MywgIlRhc2sgQSJ9KTsKICAgIHBxLnB1c2goezUsICJUYXNrIEIifSk7CiAgICBwcS5wdXNoKHsxLCAiVGFzayBDIn0pOwoKICAgIC8vIFBlZWsKICAgIGNvdXQgPDwgIlRvcCBQcmlvcml0eTogIiA8PCBwcS50b3AoKS5zZWNvbmQgPDwgIiAoUHJpb3JpdHkgIiA8PCBwcS50b3AoKS5maXJzdCA8PCAiKVxuIjsKCiAgICAvLyBEZWxldGlvbgogICAgcHEucG9wKCk7IC8vIHJlbW92ZXMgIlRhc2sgQiIKCiAgICAvLyBQZWVrIGFmdGVyIGRlbGV0aW9uCiAgICBjb3V0IDw8ICJOZXh0IFRvcCBQcmlvcml0eTogIiA8PCBwcS50b3AoKS5zZWNvbmQgPDwgIiAoUHJpb3JpdHkgIiA8PCBwcS50b3AoKS5maXJzdCA8PCAiKVxuIjsKCiAgICAvLyBVcGRhdGUgUHJpb3JpdHk6IFJlaW5zZXJ0ICJUYXNrIEMiIHdpdGggbmV3IGhpZ2hlciBwcmlvcml0eQogICAgcHEucHVzaCh7NiwgIlRhc2sgQyAoVXBkYXRlZCkifSk7CgogICAgLy8gUGVlayBhZ2FpbgogICAgY291dCA8PCAiQWZ0ZXIgVXBkYXRpbmc6ICIgPDwgcHEudG9wKCkuc2Vjb25kIDw8ICIgKFByaW9yaXR5ICIgPDwgcHEudG9wKCkuZmlyc3QgPDwgIilcbiI7CgogICAgcmV0dXJuIDA7Cn0K

Output:

Top Priority: Task B (Priority 5)
Next Top Priority: Task A (Priority 3)
After Updating: Task C (Updated) (Priority 6)

Explanation:

In the above code example-

1. We include necessary headers for input-output, priority queue, and vector functionalities.
2. We define a max-heap priority queue that stores pairs of integers and strings — the integer represents priority, and the string holds the task name.
3. We insert three tasks with different priorities: Task A (3), Task B (5), and Task C (1).
4. We use pq.top() to peek at the highest-priority task, which is "Task B" since it has the highest number (5).
5. We remove the top task using pq.pop(), which deletes "Task B".
6. We peek again, and now "Task A" becomes the top priority with value 3.
7. We simulate updating a task’s priority by reinserting "Task C" with a new higher priority (6) under the label "Task C (Updated)".
8. We peek again and see the updated task at the top, showing the new highest priority is now 6.

Real-World Applications Of Priority Queues

Priority queues are not just theoretical data structures; they are foundational in many real-world systems where the order of processing matters based on importance or urgency. Here are some practical areas where they shine:

1. Operating Systems (CPU Scheduling)

In multitasking environments, processes are assigned different priorities. A priority queue is used to ensure that high-priority processes are allocated CPU time before others.

• Example: Real-time operating systems where urgent tasks (like medical monitoring) must run before routine background jobs.

2. Dijkstra’s and A Algorithms (Pathfinding)*

Graph-based algorithms like Dijkstra’s Shortest Path or A* rely on priority queues to select the next node with the lowest cumulative cost.

• Widely used in GPS navigation systems and game AI for optimal path calculations.

3. Data Compression (Huffman Coding)

Priority queues are used in building Huffman Trees, where characters with lower frequencies are given lower priority.

• Useful in file compression tools like ZIP, JPEG, and MP3 encoding.

4. Network Traffic Management

Routers and switches often use priority queues to manage network packets, ensuring high-priority traffic (like voice or video) is sent before less critical data (like emails).

• This improves Quality of Service (QoS) in communication networks.

5. Event-Driven Simulations

In simulations (e.g., airport traffic control or bank queues), events are scheduled based on their timestamps. Priority queues help process events in chronological order.

6. Emergency Room Systems

In hospital ER software, patients are triaged based on urgency. A priority queue ensures that critical patients are treated first, even if they arrived later.

7. AI & Machine Learning Task Scheduling

In distributed ML training or inference pipelines, tasks with higher impact or faster feedback are prioritized using priority queues to optimize performance and resource usage.

8. Printer and Job Scheduling Systems

Print jobs are often assigned a priority (e.g., admin jobs may get processed before regular users), and a priority queue helps order them accordingly.

Advantages Of Priority Queues

1. Efficient Handling of Priority-Based Tasks: Priority queues allow systems to handle urgent or important tasks before others, which is critical in areas like CPU scheduling, real-time systems, or emergency response systems.
2. Support for Dynamic Priority Changes: In implementations like heaps or balanced trees, you can update the priority of elements (although it may involve reinsertion), enabling adaptive decision-making.
3. Flexible Implementations: Priority queues can be implemented using arrays, heaps, or trees, giving developers flexibility to optimize based on specific use cases (e.g., speed vs. memory usage).
4. Integral to Many Algorithms: They are foundational for graph algorithms like Dijkstra's, Prim's, and A*, and are also used in Huffman encoding, simulations, and task scheduling.
5. Predictable Performance: Heaps, the most common implementation, guarantee logarithmic time for insertions and deletions, making performance more predictable than linear search or sort-based methods.

Disadvantages Of Priority Queues

1. Complexity in Updating Priorities: Many standard libraries (like C++ STL) do not support direct priority updates, requiring workaround approaches like reinsertion, which can be inefficient.
2. No Constant-Time Search: Unlike hash maps or arrays, priority queues do not support efficient random access or search — they only give access to the highest (or lowest) priority element.
3. Overhead in Maintaining Order: Especially in sorted list or tree-based implementations, maintaining order can lead to higher insertion or deletion costs.
4. Duplicate Priorities Can Be Tricky: Handling elements with equal priorities can be ambiguous without extra mechanisms like timestamps or secondary keys.
5. Limited Use in Some Applications: In cases where priority is not a concern, simpler structures like queues, stacks, or arrays may be more straightforward and efficient.

Conclusion

Priority queues are a powerful extension of the traditional queue, enabling elements to be processed based on urgency or importance rather than arrival order. From managing CPU scheduling in operating systems to optimizing pathfinding in algorithms like Dijkstra’s and A*, priority queues form the backbone of numerous critical systems in computer science.

Understanding their various implementations—ranging from simple arrays to efficient binary heaps and balanced trees—empowers developers to make informed choices depending on the problem at hand. While they come with their own trade-offs, such as limited support for direct priority updates or constant-time search, their advantages in structured task handling and algorithmic efficiency far outweigh the limitations in most real-world scenarios.

By mastering priority queues, one gains a deeper grasp of both data structure fundamentals and the practical applications that drive software systems in the real world.

Frequently Asked Questions

Q. What is the difference between a queue and a priority queue?

A queue follows the First-In-First-Out (FIFO) principle, while a priority queue serves elements based on their priority, not just their order of arrival. The element with the highest priority is always processed first, regardless of when it was added.

Q. Which data structure is commonly used to implement a priority queue?

The most efficient and commonly used data structure is a binary heap, which allows insertion and deletion operations in O(log n) time. Other implementations include unsorted/sorted arrays, linked lists, and balanced trees like Red-Black Trees.

Q. Can a priority queue contain duplicate priorities?

Yes, a priority queue can contain multiple elements with the same priority. However, how these are handled depends on the implementation. Some systems may process them in the order they were added (FIFO within priority), while others may use additional rules.

Q. Is it possible to update the priority of an element in a priority queue?

This depends on the implementation. In many built-in libraries (like std::priority_queue in C++), direct priority updates are not supported. A common workaround is to remove the element and reinsert it with the new priority.

Q. Where are priority queues used in real life?

They are widely used in operating systems (task scheduling), network traffic control, pathfinding algorithms (like A*), data compression (Huffman coding), and even in simulations where events must be processed based on their time or urgency.

Suggested Reads: 

1. What Is Selection Sort Algorithm? Explained With Code Examples
2. Learn All About Bubble Sort Algorithm (With Code Examples)
3. Merge Sort Algorithm | Working, Applications & More (+Examples)
4. Quick Sort Algorithm | Working, Applications & More (+Examples)
5. Heap Sort Algorithm - Working And Applications (+ Code Examples)