Priority Queue in Data Structure

Last Updated on March 2, 2023 by Prepbytes

A priority queue is a type of queue data structure where each element is assigned a priority and elements with higher priority are served before elements with lower priority. It operates on the principle of "first in, first out" (FIFO), but with the added rule that elements with higher priority are dequeued before elements with lower priority. This means that the order of elements in the queue is determined by their priority, rather than the order in which they were added to the queue.

Consider a priority queue to be a line of patients at a hospital. The priority order is determined by the patient’s situation. The patient with the most serious injury would be first in line.

Characteristics of Priority Queue in Data Structure

The following are the characteristics of a priority queue in data structure:

1. Element Priorities: Each element in the queue is assigned a priority, determining the order in which elements are processed.
2. Dynamic Priorities: The priority of elements can be changed dynamically, allowing for efficient updates to the queue as priorities change.
3. Ordered Processing: Elements with higher priority are processed before elements with lower priority, regardless of their order in the queue.
4. Efficient Access: Priority queues allow for efficient access to the highest-priority element in the queue.
5. Time Optimization: By prioritizing elements in the queue, the average time to process elements can be reduced compared to a standard queue.
6. Flexible Implementation: Priority queues can be implemented in a variety of ways, including arrays, linked lists, and binary heaps, allowing for the choice of the best implementation for a particular use case.
7. Resource Allocation: Priority queues can be used for efficient resource allocation, such as CPU time or memory, based on the priority of tasks or processes.
8. Priority-Based Processing: Priority queues allow for processing elements in order of their priority, making it a useful data structure for implementing algorithms that require prioritization.

Types of Priority Queue in Data Structure

There are two types of priority queue based on the priority of elements.

• Min Priority Queue
• Max Priority Queue

Min Priority Queue

A min priority queue gives the highest priority to the smallest number in that queue. For example, we have seven numbers in the priority queue which are 4, 12, 6, 35, 25, 40, 2. To start, we’ll sort these numbers in ascending order. The new list is as follows: 2, 4, 6, 12, 25, 35, 40. In this list, 2 is the smallest number. Hence, the min priority queue treats number 2 as the highest priority.

Max Priority Queue

A max priority queue gives the highest priority to the highest number in that queue. For example, you have seven numbers in the priority queue which are 4, 12, 6, 35, 25, 40, 2. To start, we’ll sort these numbers in descending order. The new list is as follows: 40, 35, 25, 12, 6, 4, 2. The highest number on this list is 40. Hence, the max priority queue treats number 40 as the highest priority.

Implementation of Priority Queue in Data Structure

Priority queue can be implemented in one of the following ways:

• Array
• Linked List
• Binary Search Tree
• Hashmap
• Binary Heap

The binary heap is the most efficient approach for implementing the priority queue in the data structure.

The table below highlights the complexities of various operations in a priority queue.

Binary Heap

Binary Heap is a complete binary tree-based data structure that implements a priority queue. A binary heap tree arranges the tree’s parent and child nodes in a specific order. A parent node in a binary heap tree can contain a maximum of two child nodes. The parent node’s value could be either:

• A value that is equal to or less than the value of a child node.
• The value of a child node must be equal to or greater than its value.

The previous approach splits the binary heap into two types: max heap and min heap.

Max-Heap: In a max-heap, the parent node is always greater than or equal to its child nodes, with the largest element at the root.

Min-Heap: In a min-heap, the parent node is always smaller than or equal to its child nodes, with the smallest element at the root.

Binary heaps have efficient insertion, deletion, and access times, making them a popular choice for implementing priority queues. The height of a binary heap is logarithmic in the number of elements, resulting in an efficient performance for large data sets.

Binary heaps are often implemented as arrays, with the relationship between parent and child nodes maintained through simple arithmetic operations on array indices. This compact representation makes binary heaps space-efficient and easy to implement.

Priority Queue using Binary Heap

Generally, Binary heaps are preferred for the implementation of priority queue because heaps provide better performance as compared to arrays or linked lists.
Operations of Binary heaps are:

• Insert(): This function is used to insert an element into the priority queue.
• remove(): This function is used to remove the element from the priority queue.
• extractMax(): This function is used to extract the element with the highest priority.
• getmax(): This function is used to return the maximum priority element.
• ChangePriority(): This function is used to change the priority of the element.

Program of Priority Queue Using Binary Heap**

#include <bits/stdc++.h>
using namespace std;

int H[50];
int size = -1;


int parent(int i)
{

    return (i - 1) / 2;
}

int leftChild(int i)
{

    return ((2 * i) + 1);
}

int rightChild(int i)
{

    return ((2 * i) + 2);
}

void shiftUp(int i)
{
    while (i > 0 && H[parent(i)] < H[i]) {

    
        swap(H[parent(i)], H[i]);

    
        i = parent(i);
    }
}

void shiftDown(int i)
{
    int maxIndex = i;

    // Left Child
    int l = leftChild(i);

    if (l <= size && H[l] > H[maxIndex]) {
        maxIndex = l;
    }

    // Right Child
    int r = rightChild(i);

    if (r <= size && H[r] > H[maxIndex]) {
        maxIndex = r;
    }

    if (i != maxIndex) {
        swap(H[i], H[maxIndex]);
        shiftDown(maxIndex);
    }
}

void insert(int p)
{
    size = size + 1;
    H[size] = p;

    shiftUp(size);
}

int extractMax()
{
    int result = H[0];

    H[0] = H[size];
    size = size - 1;

    shiftDown(0);
    return result;
}

void changePriority(int i, int p)
{
    int oldp = H[i];
    H[i] = p;

    if (p > oldp) {
        shiftUp(i);
    }
    else {
        shiftDown(i);
    }
}


int getMax()
{

    return H[0];
}

void remove(int i)
{
    H[i] = getMax() + 1;

    
    shiftUp(i);

    extractMax();
}

int main()
{

    /*         45
            /     \
        31     14
        / \ / \
        13 20 7 11
        / \
    12 7
    Create a priority queue shown in
    example in a binary max heap form.
    Queue will be represented in the
    form of array as:
    45 31 14 13 20 7 11 12 7 */

    // Insert the element to the
    // priority queue
    insert(55);
    insert(20);
    insert(14);
    insert(12);
    insert(31);
    insert(7);
    insert(11);
    insert(13);
    insert(7);

    int i = 0;

    // Priority queue before extracting max
    cout << "Priority Queue : ";
    while (i <= size) {
        cout << H[i] << " ";
        i++;
    }

    cout << "\n";

    // Node with maximum priority
    cout << "Node with maximum priority : "
        << extractMax() << "\n";

    // Priority queue after extracting max
    cout << "Priority queue after "
        << "extracting maximum : ";
    int j = 0;
    while (j <= size) {
        cout << H[j] << " ";
        j++;
    }

    cout << "\n";

    // Change the priority of element
    // present at index 2 to 49
    changePriority(2, 49);
    cout << "Priority queue after "
        << "priority change : ";
    int k = 0;
    while (k <= size) {
        cout << H[k] << " ";
        k++;
    }

    cout << "\n";

    // Remove element at index 3
    remove(3);
    cout << "Priority queue after "
        << "removing the element : ";
    int l = 0;
    while (l <= size) {
        cout << H[l] << " ";
        l++;
    }
    return 0;
}

import java.util.*;
class PrepBytes{

static int []H = new int[50];
static int size = -1;


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


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

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

static void shiftUp(int i)
{
while (i > 0 &&
        H[parent(i)] < H[i])
{
    // Swap parent and current node
    swap(parent(i), i);

    // Update i to parent of i
    i = parent(i);
}
}

static void shiftDown(int i)
{
int maxIndex = i;

// Left Child
int l = leftChild(i);

if (l <= size &&
    H[l] > H[maxIndex])
{
    maxIndex = l;
}

// Right Child
int r = rightChild(i);

if (r <= size &&
    H[r] > H[maxIndex])
{
    maxIndex = r;
}

if (i != maxIndex)
{
    swap(i, maxIndex);
    shiftDown(maxIndex);
}
}

static void insert(int p)
{
size = size + 1;
H[size] = p;

shiftUp(size);
}


static int extractMax()
{
int result = H[0];

H[0] = H[size];
size = size - 1;


shiftDown(0);
return result;
}

static void changePriority(int i,
                        int p)
{
int oldp = H[i];
H[i] = p;

if (p > oldp)
{
    shiftUp(i);
}
else
{
    shiftDown(i);
}
}

static int getMax()
{
return H[0];
}

static void remove(int i)
{
H[i] = getMax() + 1;


shiftUp(i);

// Extract the node
extractMax();
}

static void swap(int i, int j)
{
int temp= H[i];
H[i] = H[j];
H[j] = temp;
}

public static void main(String[] args)
{

insert(55);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);

int i = 0;

// Priority queue before extracting max
System.out.print("Priority Queue : ");
while (i <= size)
{
    System.out.print(H[i] + " ");
    i++;
}

System.out.print("\n");

// Node with maximum priority
System.out.print("Node with maximum priority : " +
                    extractMax() + "\n");

// Priority queue after extracting max
System.out.print("Priority queue after " +
                "extracting maximum : ");
int j = 0;
while (j <= size)
{
    System.out.print(H[j] + " ");
    j++;
}

System.out.print("\n");

// Change the priority of element
// present at index 2 to 49
changePriority(2, 49);
System.out.print("Priority queue after " +
                "priority change : ");
int k = 0;
while (k <= size)
{
    System.out.print(H[k] + " ");
    k++;
}

System.out.print("\n");

// Remove element at index 3
remove(3);
System.out.print("Priority queue after " +
                "removing the element : ");
int l = 0;
while (l <= size)
{
    System.out.print(H[l] + " ");
    l++;
}
}
}

Output

Priority Queue : 55 31 14 13 20 7 11 12 7 
Node with maximum priority : 55
Priority queue after extracting maximum : 31 20 14 13 7 7 11 12 
Priority queue after priority change : 49 20 31 13 7 7 11 12 
Priority queue after removing the element : 49 20 31 12 7 7 11

Time Complexity:
Insertion: O(Log N)
Deletion: O(Log N)
Peek: O(1)

Advantages of using Priority Queue

The advantages of using a priority queue in data structure, include:

1. Efficient Access: Priority queues allow for efficient access to the highest-priority element in the queue. This is often done in O(1) time with a binary heap.
2. Dynamic Priority Assignment: The priority of an element in the queue can be changed dynamically, allowing for efficient updates to the queue as priorities change.
3. Flexibility: Priority queues can be implemented in a variety of ways, including arrays, linked lists, and binary heaps. This allows for the choice of the best implementation for a particular use case.
4. Priority-Based Processing: Priority queues allow for processing elements in order of their priority, making it a useful data structure for implementing algorithms that require prioritization.
5. Time Optimization: By prioritizing elements in the queue, the average time to process elements can be reduced compared to a standard queue.
6. Resource Allocation: Priority queues can be used for efficient resource allocation, such as CPU time or memory, based on the priority of tasks or processes.

Disadvantages of using Priority Queue

The disadvantages of using a priority queue in data structure, include:

1. Complexity: Priority queues can be more complex to implement and maintain compared to other data structures such as arrays or linked lists.
2. Priority Conflicts: Determining the priority of elements can be challenging, and conflicts may arise when two elements have the same priority.
3. Performance Overhead: Updating the priority of elements in the queue can be slow, especially for larger queues, leading to performance overhead.
4. Unpredictable Performance: The performance of a priority queue can be unpredictable if the priority of elements changes frequently, causing the queue to be constantly rearranged.
5. Priority Inversion: Priority inversion can occur when a high-priority task is blocked by a lower-priority task, leading to suboptimal performance.
6. Implementation Dependent: The performance of a priority queue can vary significantly based on the implementation chosen, making it important to choose the right implementation for the task at hand.

Uses of Priority Queue

There is a variety of uses for the Priority queue in data structure, including:

1. Scheduling: Prioritizing and scheduling tasks based on their priority.
2. Resource allocation: Allocating resources such as memory or CPU time to processes based on their priority.
3. Graph algorithms: Used in algorithms such as Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.
4. Simulation: Prioritizing events in a simulation based on their time of occurrence.
5. Medical Systems: In triage systems assigning priorities to patients based on the severity of their conditions.
6. Video Games: Used for determining the order in which objects are rendered on the screen.
7. Network Routing: Used in routing algorithms for prioritizing packets.
8. Indexing: Used in databases and search engines for prioritizing search results based on relevance.

Real-life Applications of Priority Queue

Priority queue in data structure has many real-life applications, some of which include:

1. Operating Systems: Task scheduling and resource allocation in operating systems are often implemented using priority queues.
2. Networking: Network routers use priority queues to manage incoming packets and prioritize their processing based on their priority.
3. Medical Treatment: Hospitals use priority queues to manage patient care, prioritizing patients based on their medical urgency.
4. Air Traffic Control: Air traffic control systems use priority queues to manage the flow of aircraft, prioritizing landing and takeoff requests based on factors such as weather conditions and aircraft type.
5. Financial Trading: Financial trading systems use priority queues to manage trades, prioritizing the processing of trades based on factors such as their size and urgency.
6. Customer Service: Customer service systems use priority queues to manage customer requests, prioritizing requests based on factors such as their urgency and the customer’s status.
7. Web Search: Web search engines use priority queues to manage the processing of web pages, prioritizing the indexing of pages based on their relevance and importance.
8. GPS Navigation: GPS navigation systems use priority queues to manage route calculation and updates, prioritizing routes based on factors such as traffic conditions and road speeds.

Conclusion
The Priority Queue is a useful data structure for dealing with items with varied priorities. The primary benefit of having a priority queue is that you can quickly access the highest priority item with a time complexity of only O(1). The sole drawback to employing Priority Queue is that the enqueue and dequeue operations are slow and have a time complexity of O(log n).