Priority Queue Data Structure

Priority Queue Data Structure

Priority queue data structure is a queue in which we are able to insert or remove items from any position based on some property( such as priority of the task to be procedded) is often referred to as priority queue.

A priority cam be conceptualized as a aeries of queues representing situations in which it knows what priorities are associated with queue items.

Implemention of Priority Queue

Following data structure is used to implement priority queue

• Arrays
• Linked list
• Heap data structure
• Binary search tree

 

Program for Priority queue

#include <bits/stdc++.h>
using namespace std;
 
// Structure for the elements
    struct item {
    int value;
    int priority;
};
 
// Store the element 
item pr[100000];
 
// Pointer to the last index
int size = -1;
 
// Function to insert a new element
void enqueue(int value, int priority)
{
    // Increase the size
    size++;
 
    // Insert the element
    pr[size].value = value;
    pr[size].priority = priority;
}
 
// Function to check the top element
int peek()
{
    int highestPriority = INT_MIN;
    int ind = -1;
 
      for (int i = 0; i <= size; i++) {
 
      
        if (highestPriority == pr[i].priority && ind > -1
            && pr[ind].value < pr[i].value) {
            highestPriority = pr[i].priority;
            ind = i;
        }
        else if (highestPriority < pr[i].priority) {
            highestPriority = pr[i].priority;
            ind = i;
        }
    }
 
    return ind;
}
 
// Function to remove the element with the highest priority
void dequeue()
{
   
    int ind = peek();
 
   
    for (int i = ind; i < size; i++) {
        pr[i] = pr[i + 1];
    }
 
    // Decrease the size of the priority queue by one
    size--;
}
 
int main()
{
    // Function Call to insert elements
    enqueue(10, 2);
    enqueue(14, 4);
    enqueue(16, 4);
    enqueue(12, 3);
 
    // Stores the top element
    int ind = peek();
 
    cout << pr[ind].value << endl;
 
    // Dequeue the top element
    dequeue();
 
    // Check the top element
    ind = peek();
    cout << pr[ind].value << endl;
 
    // Dequeue the top element
    dequeue();
 
    // Check the top element
    ind = peek();
    cout << pr[ind].value << endl;
 
    return 0;
}

Output

16
14
12

 

 

Analysis of complexities 

Implementation	add	Remove	peek
Linked list	O(1)	O(n)	O(n)
Binary heap	O(logn)	O(logn)	O(1)
Binary search tree	O(logn)	O(logn)	O(1)

 

Characteristics of a Priority queue

Characteristics of priority queue are follows:

• Every element has a priority  related with it.
• An element with the higher priority will be dequeued before the deletion of the low priority.
• If two elements have the same priority, they are arranged using the FIFO principle.

 

Types of Priority Queue

1. Ascending order priority queue
2. Descending order priority queue

 

 

1. Ascending order priority queue

 In ascending order priority queue, a low priority number is given as a high priority.

For example,

Suppose the numbers from 1 to 5 arranged in an ascending order like 1,2,3,4,5, then the smallest number 1 is given as the high priority in a priority queue.

 

2. Descending order priority queue

In descending order priority queue, a high priority number is given as a high priority in a priority.

For example,

Suppose numbers from 1 to 5 arranged in descending order like 5, 4, 3, 2, 1  then 5 is  largest number. So 5 is given as the high priority in a priority queue.

 

 

 

Applications of Prority Queues

• Operating systems, Scheduling of Jobs
• Networks communications, to manage limited bandwidth
• Simulation modeling, to manage discrete events

 

Read more, Circular Queue Data Structure