Priority Queue in Data Structure: Types, Implementation & More

Updated on September 30, 2024

Article Outline

What is a Priority Queue?Types of Priority Queues Implementation of Priority Queues Operations on Priority Queues Applications of Priority Queues Advantages and Disadvantages of Priority Queues Conclusion FAQs

A priority queue is a data structure that arranges the elements according to the priority. Priority queue stands as an abstract data structure that allows adding and removing elements similar to a regular queue but each element has been provided with a priority. Priority queues are mostly frequented by certain algorithms such as Dijkstra’s shortest path algorithm, Huffman coding, and various types of scheduling algorithms among others.

Every priority queue has a distinct purpose and is necessary to efficiently manage a range of job priorities. Their versatility is essential for properly resolving a wide range of computer science issues. They are extensively employed in software development to efficiently handle different components. In this article, we will explain the priority queues, their types and implementation, what operations they behave in, and which applications, as well as a comparison of their benefits and drawbacks.

What is a Priority Queue?

A priority queue is a data structure that operates like a regular queue but with priority levels for each element. Instead of maintaining the first-in-first-out (FIFO) order, the priority queue serves the highest (or lowest) priority element first. This abstract data type offers a means of keeping the dataset up to date. The order in the “normal” queue is first-in, first-out. Elements are dequeued in the same order that was used during the insertion process.

On the other hand, the priority of an element within a priority queue determines its order within the queue. The elements with the highest priority are moved to the front of the priority queue, while the ones with the lowest priority are moved to the back. It only accepts similar items. As a result, the data structure’s priority queue puts the elements in either ascending or descending order.

Example: A perfect example of a priority queue can be an emergency room at a hospital where patients are treated not just as served in the queue but rather, those with the most critical conditions first.

Patient P1 with a minor injury (has a lower priority) arrives first.
Patient P2 with a severe injury (has a higher priority) arrives later.
Patient P3 with a moderate injury (has a moderate priority) arrives last.

In a regular queue, the patients would be treated in the order of their arrival i.e., P1, P2, P3. But in a priority queue, they are treated in the order of their priority: P2, P3, P1.

Characteristics of a Priority Queue

Priority queues have important characteristics that are followed while using them in data structures:

Every element has a priority associated with it.
Elements with higher priority are dequeued first.
If two elements have the same priority, they are dequeued according to their order in the queue (in case of a stable priority queue).

Get curriculum highlights, career paths, industry insights and accelerate your technology journey.

Download brochure

Types of Priority Queues

There are two types of priority queues which can be categorised as follows:

Min-Priority Queue

In the min-priority queue, the goal is to first remove or dequeue the element with minimum priority. This means the element with the lowest priority value is stored in the front for removal when dequeuing. About the insertion of new elements, they are inserted in the order of their priorities in such a manner that the order of min-priority is preserved.

Concerning dequeuing, the element with the least (but highly ranked) priority value is targeted first. This type of priority queue is suitable when the management of elements with the least priority is topmost, that is, all very low-priority tasks or data seems to be processed as a foremost concern. This type of priority queue is useful in algorithms where you want to process the “cheapest” or “least” item first, such as Dijkstra’s shortest path algorithm.

For example, suppose you have a queue of tasks, with the following priorities:

Task 1 with priority 4
Task 2 with priority 2
Task 3 with priority 5
Task 4 with priority 1

In a min-priority queue, tasks are processed starting from the task with the lowest priority number. So, the order of execution would be:

Task 4 (priority 1)
Task 2 (priority 2)
Task 1 (priority 4)
Task 3 (priority 5)

In this example, Task 4 is the first to be processed as it has the lowest priority number. Next in line is Task 3, and so on. With the fewest number of tasks, the most critical or urgent activities are guaranteed to be completed first in this kind of queue.

Max-Priority Queue

In the max-priority queue, the goal is to first remove or deque the item with the maximum priority. This order is maintained when placing new items on the list. With regard to dequeuing, the element with the greatest priority level with the most weight in terms of importance is the one to become first in retrieval.

Max-priority queues are useful in scenarios where you want to process the most important or largest element first, such as in certain scheduling algorithms of the OS where tasks with higher priorities must be executed before others.

For example, suppose you have a queue of tasks, with the following priorities:

Task 1 with priority 4
Task 2 with priority 2
Task 3 with priority 5
Task 4 with priority 1

In a max-priority queue, tasks are processed starting from the task with the highest priority. So, the order of execution would be:

Task 3 (priority 5)
Task 1 (priority 4)
Task 2 (priority 2)
Task 4 (priority 1)

In this example, Task 3 is the first to be processed as it has the highest priority number. Next in line is Task 1, and so on. This type of queue ensures that the most critical tasks (with the largest number) are handled first.

Implementation of Priority Queues

There are several approaches to implement priority queues based on the performance needed. Some of the most widely used implementations are balanced binary search trees, heaps, and arrays. Let’s see them one by one in detail and with examples:

Binary Heaps

Binary heaps are the most efficient way to implement priority queues because they allow us to insert elements and access the highest or lowest priority element in logarithmic time. A binary heap is defined to be a complete binary tree that satisfies the heap property: the key stored at each node is either greater or less than (in min-heaps and max-heaps, respectively) the keys of its children.

C++ Code:

#include <iostream>

#include <vector>

class MinHeap {

    std::vector heap;

    // Helper function to heapify up

    void shiftUp(int index) {

        while (index != 0 && heap[parent(index)] > heap[index]) {

            std::swap(heap[index], heap[parent(index)]); // Swap with the parent if smaller

            index = parent(index);

        }

    }

    // Helper function to heapify down

    void shiftDown(int index) {

        int left = leftChild(index);

        int right = rightChild(index);

        int smallest = index;

        // Compare with the left child

        if (left < heap.size() && heap[left] < heap[smallest])

            smallest = left;

        // Compare with the right child

        if (right < heap.size() && heap[right] < heap[smallest])

            smallest = right;

        // Swap with the smallest child and recurse

        if (smallest != index) {

            std::swap(heap[index], heap[smallest]);

            shiftDown(smallest);

        }

    }

    // Helper functions to find parent, left, and right children

    int parent(int i) { return (i - 1) / 2; }

    int leftChild(int i) { return 2 * i + 1; }

    int rightChild(int i) { return 2 * i + 2; }

public:

    // Insert a new element into the heap

    void push(int val) {

        heap.push_back(val);

        shiftUp(heap.size() - 1); // Maintain heap property

    }

    // Remove the top element

    void pop() {

        if (heap.size() == 0) return;

        heap[0] = heap.back(); // Replace root with last element

        heap.pop_back();

        shiftDown(0); // Maintain heap property

    }

    // Return the top element (smallest in min-heap)

    int top() {

        if (heap.size() == 0) return -1;

        return heap[0];

    }

    // Check if the heap is empty

    bool empty() {

        return heap.size() == 0;

    }

};

int main() {

    MinHeap pq;

    pq.push(40);

    pq.push(30);

    pq.push(25);

    pq.push(10);

    pq.push(5);

    std::cout << "The top element is: " << pq.top() << std::endl;

    pq.pop();

    std::cout << "The top element after pop is: " << pq.top() << std::endl;
    
    return 0;

}

Output:

The top element is: 5

The top element after pop is: 10

Explanation:

In this C++ implementation, we used a min-heap to represent a priority queue. When elements are inserted, after maintaining the heap property, we heapify up (compare new element with parent). When the top element (smallest) is removed, to maintain order, we heapify down (compare the new root with children). This will always put the smallest element at the top.

Also Read: Difference Between Stack and Queue Data Structures

Java Code:

import java.util.PriorityQueue;

public class MinHeapExample {

    public static void main(String[] args) {

        // Creating a priority queue (min-heap)

        PriorityQueue pq = new PriorityQueue<>();

        

        // Inserting elements

        pq.add(40);

        pq.add(30);

        pq.add(25);

        pq.add(10);

        pq.add(5);

        

        // Display top element

        System.out.println("The top element is: " + pq.peek());

        

        // Remove the top element

        pq.poll();

        

        // Display top element after removal

        System.out.println("The top element after pop is: " + pq.peek());

    }

}

Output:

The top element is: 5

The top element after pop is: 10

Explanation:

In Java implementation, we use the PriorityQueue class directly from the Java Collections, which is actually not a heap but a binary heap. The default behaviour of PriorityQueue is based on the min heap. This means that by adding elements, the queue will try to keep the smallest one on the top. The function peek() returns the element from the top, while with the function poll(), a top element is removed from the heap.

Binary Search Trees

A priority queue can be implemented using a binary search tree (BST). In this data structure, the leftmost node will store the highest priority element (to make a max-priority queue) or the rightmost node will store the lowest element (to make a min-priority queue). The operations are typically all O(log n) except that sometimes insertions and deletions can be O(n) if not somewhat self-balancing. It is because this tree could easily become unbalanced, so the performance can get very bad.

C++ Code:

#include <iostream>
// Create a node structure

struct Node {

    int data;

    Node* left;

    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}

};

// Create a class for BSTPriorityQueue

class BSTPrQ {

    Node* root;

    // Helper function to insert a node in the BST

    Node* insert(Node* root, int data) {

        if (root == nullptr)

            return new Node(data);

        if (data < root->data)

            root->left = insert(root->left, data);

        else

            root->right = insert(root->right, data);

        return root;

    }

    // Helper function to find the minimum node in the BST

    Node* findMin(Node* root) {

        while (root && root->left)

            root = root->left;

        return root;

    }

    // Helper function to remove a node from the BST

    Node* remove(Node* root, int data) {

        if (root == nullptr)

            return nullptr;

        if (data < root->data)

            root->left = remove(root->left, data);

        else if (data > root->data)

            root->right = remove(root->right, data);

        else {

            if (root->left == nullptr) {

                Node* temp = root->right;

                delete root;

                return temp;

            } else if (root->right == nullptr) {

                Node* temp = root->left;

                delete root;

                return temp;

            }

            Node* temp = findMin(root->right);

            root->data = temp->data;

            root->right = remove(root->right, temp->data);

        }

        return root;

    }

public:

    BSTPrQ() : root(nullptr) {}

    // Member functions

    void push(int data) {

        root = insert(root, data);

    }

    void pop() {

        if (root)

            root = remove(root, findMin(root)->data);

    }

    int top() {

        Node* minNode = findMin(root);

        return minNode ? minNode->data : -1;

    }

   bool empty() {

        return root == nullptr;

    }

};

int main() {

    BSTPrQ pq;

    pq.push(10);

    pq.push(30);

    pq.push(20);

    pq.push(5);

    std::cout << "The top element is: " << pq.top() << std::endl;

    pq.pop();

    std::cout << "The top element after pop is: " << pq.top() << std::endl;
    
    return 0;

}

Output:

The top element is: 5

The top element after pop is: 10

Explanation:

In this BST implementation of a priority queue, the elements would be inserted such that smaller elements are threaded towards the left subtree and larger elements towards the right subtree. It retrieves the smallest element (leftmost node) with the top() function. To remove the smallest element, we delete the leftmost node and adjust the tree accordingly. The binary search tree provides efficient insertion and removal but can degrade to O(n) if unbalanced.

Java Code:

// Create a priority queue using a binary search tree (BST)

class Node {

    int data;

    Node left, right;

    public Node(int data) {

        this.data = data;

        left = right = null;

    }

}

class BSTPrQ {

    Node root;

    public BSTPrQ() {

        root = null;

    }

    // Insert a node into the BST

    Node insert(Node root, int data) {

        if (root == null) {

            return new Node(data);

        }

        if (data < root.data) {             root.left = insert(root.left, data);         } else if (data > root.data) {

            root.right = insert(root.right, data);

        }

        return root;

    }

    // Find the minimum node in the BST

    Node findMin(Node root) {

        while (root.left != null) {

            root = root.left;

        }

        return root;

    }

    // Remove a node from the BST

    Node remove(Node root, int data) {

        if (root == null) return root;

        if (data < root.data) {             root.left = remove(root.left, data);         } else if (data > root.data) {

            root.right = remove(root.right, data);

        } else {

            if (root.left == null) return root.right;

            if (root.right == null) return root.left;

            Node temp = findMin(root.right);

            root.data = temp.data;

            root.right = remove(root.right, temp.data);

        }

        return root;

    }

    // Get the top (min) element

    int top() {

        if (root == null) return -1;

        return findMin(root).data;

    }

    // Insert element into the priority queue

    void push(int data) {

        root = insert(root, data);

    }

    // Remove the top element

    void pop() {

        root = remove(root, top());

    }

    // Check if the queue is empty

    boolean isEmpty() {

        return root == null;

    }

}

public class Main {

    public static void main(String[] args) {

        BSTPrQ pq = new BSTPrQ();
       
       pq.push(40);

        pq.push(50);

        pq.push(10);

        pq.push(20);

        System.out.println("The top element is: " + pq.top());

        pq.pop();

        System.out.println("The top element after pop is: " + pq.top());

    }

}

Output:

The top element is: 10

The top element after pop is: 20

Explanation:

The binary search tree for a priority queue implemented in Java functions similarly to that of C++. The queue keeps the smaller elements on the left to maintain priority. Using the BST structure, the push() method inserts items, and pop() removes the smallest element.

Arrays

Arrays can also be used to implement a priority queue. It is not the best method or efficient way, but it works. In most implementations, arrays have to be sorted after every insertion. In others, you would traverse the array to find the element with the highest or lowest priority.

C++ Code:

#include <iostream>
#include <vector>
#include <algorithm>

class PQ {

    std::vector arr;

public:

    // Insert an element into the array

    void push(int val) {

        arr.push_back(val); // O(1) insertion

    }

    // Remove the minimum element from the array

    void pop() {

        if (arr.empty()) return;

        // Find the minimum element

        auto minIt = std::min_element(arr.begin(), arr.end()); // O(n) search for minimum

        arr.erase(minIt); // O(n) removal

    }


    // Return the minimum element

    int top() {

        if (arr.empty()) return -1;

        return *std::min_element(arr.begin(), arr.end()); // O(n) search for minimum

    }

    // Check if the array is empty

    bool empty() {

        return arr.empty();

    }

};


int main() {

    PQ pq;
    
    pq.push(50);

    pq.push(40);

    pq.push(30);

    pq.push(20);

    pq.push(5);

    std::cout << "The top element is: " << pq.top() << std::endl;

    pq.pop();

    std::cout << "The top element after pop is: " << pq.top() << std::endl;
   
    return 0;

}

<b>Output:</b>

The top element is: 5

The top element after pop is: 20

Explanation:

In C++ implementation, we are using arrays for priority queue, elements are added to the array in a consistent amount of time by using push(). It takes O(n) time to search through the complete array to discover the least value, which is necessary to identify and eliminate the element with the highest priority (smallest number).

Java Code:

import java.util.ArrayList;

import java.util.Collections;

class PQ {

    private ArrayList arr;

    public PQ() {

        arr = new ArrayList<>();

    }

    // Insert element into the priority queue

    public void push(int data) {

        arr.add(data); // O(1)

    }

    // Remove the element with the highest priority (minimum value)

    public void pop() {

        if (arr.isEmpty()) return;

        int minElement = Collections.min(arr);

        arr.remove(Integer.valueOf(minElement)); // O(n)

    }

    // Return the element with the highest priority (minimum value)

    public int top() {

        if (arr.isEmpty()) return -1;

        return Collections.min(arr); // O(n)

    }

    // Check if the queue is empty

    public boolean isEmpty() {

        return arr.isEmpty();

    }

}

public class Main {

    public static void main(String[] args) {

        PQ pq = new PQ();

        pq.push(50);

        pq.push(40);

        pq.push(20);

        pq.push(10);

        pq.push(5);

        System.out.println("The top element is: " + pq.top());

        pq.pop();

        System.out.println("The top element after pop is: " + pq.top());

    }

}

Output:

The top element is: 5

The top element after pop is: 10

Explanation:

The C++ version and the Java array-based implementation function identically. In Java implementation, although it enables quick insertion (O(1)), finding and removing the minimal element requires O(n) time. For larger datasets, this method is less efficient than binary heaps or binary search trees, despite its simplicity.

Operations on Priority Queues

Key operations of a priority queue are similar to those of normal queues but they present rather uniquely because the queue is priority-based. Here are some of the common operations on priority queues:

1. Insert (Enqueue): Inserts an item in the priority queue with a certain priority. For heap-based implementation purposes, this takes O(log n) time because after adding some item the structure of the binary tree which dictates the heap has to be retained.

2. Delete (Dequeue): Extract and return the element with either the highest or the least priority, (depending on whether the queue is meant for max prioritisation or min prioritisation respectively). In a situation whereby heaps are used in the implementation of this operation, O(log n) time is needed because after extraction steps have to be made to restore the discrepancies showing that it is a heap.

3. Peek (Top): Gives access to the element that has a priority either highest or lowest. Since this is manipulation with the heap tree, it can therefore be safely ascertained that such an operation is O(1) since the heap is accessed at the other end.

4. IsEmpty: It looks for conditions determining whether the priority queue has elements or not. This operation is an O(1) as all it does is count the elements inside the queue.

5. Size: Returns the amount of items inside the prioritising cluster in this case. This is likewise an O(1) move as it only involves getting back the amount that has been kept in a memory position.

Applications of Priority Queues

Priority queues are extensively used in a variety of computer science domains and practical applications. Some of the applications are:

Dijkstra’s Algorithm: In Dijkstra’s shortest path algorithm, a priority queue is reserved for the node to be processed that has the least distance. In Dijkstra’s algorithm example, a min-priority queue is used in such a manner that the nodes with the least tentative distance are selected for processing first.

Huffman Encoding: In a popular compression algorithm known as Huffman encoding, a priority queue plays an important role. It uses a min-priority queue to combine two least occurring characters iteratively until the final tree is constructed.

Task Scheduling: In operating systems (OS), priority queues are used to carry out task scheduling activities. High-priority tasks are completed ahead of low-priority tasks. The same approaches are used in CPU scheduling as well as job scheduling activities, where job queuing is based on the principles of a priority queue.

Event-Driven Simulation: Looking at event-driven simulations, involve events assuming a finite set of discrete time instants where the next event can be processed using a priority queue as the next in the simulation. The time-critical ahead with the low time delays get attended to.

Load Balancing: Priority queues can also be applied in load balancing, here some tasks or servers that are deemed high are given more load (resources) than others. This guarantees that key tasks are executed with the right amount of load resources.

Systems of Real-Time Data Processing: In various real-time systems, priority queues are used to manage the processes when there is a need to have processes with different priorities. More critical tasks that are to be executed in real-time are allocated higher priorities.

Advantages and Disadvantages of Priority Queues

Advantages

Efficient Access: It usually takes O(1) time to access the element with the highest or lowest priority. It is because a priority queue’s elements can have their priority values changed, enabling the queue to dynamically rearrange itself when priorities shift.
Dynamic Data: While preserving the hierarchy of priorities, priority queues enable effective insertions and removals. Data can be dynamically reordered with the help of priority queues.
Wide-ranging Applications: Many algorithms and applications, especially those that deal with scheduling and optimization, depend on priority queues. Examples include Dijkstra’s algorithm, CPU scheduling algorithms, OS algorithms, etc.

Disadvantages

Complexity of Change Priority: In most priority queue implementations, changing an element’s priority can be a complex and inefficient process that takes O(n) on average.
Storage Overhead: To preserve the heap property, some implementations, including those that use heaps, may need more space. It can require more memory to store the priority value for every entry in a priority queue, which could be problematic for systems with constrained resources.
Not Always Stable: The stability of a priority queue might vary depending on how it is implemented. This means the items that have the same priority might not keep their current relative order.

Conclusion

Priority queues are high-performance data structures applied commonly across dynamic programming including graphs and trees. Whether the implementation is based on arrays, heaps, or trees, there are smart ways to handle elements according to their priority in programming. This speeds up most computations as it uses efficient structures like binary heaps, binary search trees, or arrays to meet the need for better system performance and response through improved computations. The principle is at the core of facilitating smoother management of assignments and their execution on most real applications within the digital ecosystem.

By knowing the types and operations of priority queues and how to implement them in languages like C++ and Java, one can optimise many algorithms and real-world systems that require priority-based task management. With their vast applications in computer science and real-world systems, mastering priority queues will enhance your understanding of how to build efficient and scalable solutions for many problems. Want to explore Data Structure? Try the Certificate Program in Application Development by Hero Vired.

FAQs

What is a priority queue?

A priority queue is a data structure where each element has a priority, and elements with higher priority are served before lower-priority elements.

What are the types of priority queues?

There are two types of priority queues: Min-Heap, in which the minimum element is the priority element, and Max-Heap, in which the maximum element is a priority.

Which data structures are used to implement priority queues?

Binary heaps, binary search trees, linked lists, as well as arrays can be used to implement priority queues. Out of all these, the fastest in terms of the insertion and deletion operations will be heaps which can be implemented in any programming language.

What is the time complexity for operations in the priority queue?

Typically in binary heaps, insertion and deletion operations will take O(log n) time complexity. In the case of array-based implementation, the insertion operation could take O(1), Deletion and Lookup operation could take O(n).

Where are priority queues used in real life?

Priority queues are useful in task scheduling (such as CPU scheduling), Dijkstra’s shortest path algorithm, Huffman coding, and various other areas that involve the processing of data of different preferences.

Updated on September 30, 2024

Link

Programs tailored for your success

Popular

IIT Courses

Management

Data Science

Finance

Technology

Future Tech

3 ASSURED INTERVIEWS

Accelerator Program in

Business Analytics and Data Science

With

Part-time · 10 months

Apply by : 23 November, 2024

Financial Analysis, Valuation, & Risk Management

3 ASSURED INTERVIEWS

Certificate Program in

Financial Analysis, Valuation, & Risk Management

With

Part-time · 7 months

Apply by : 23 November, 2024

INTERNSHIP ASSURANCE

Certificate Program in

DevOps & Cloud Engineering

With

Part-time · 7.5 months

Apply by : 23 November, 2024

Upskill with expert articles

View all

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Certification Program in Data Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance