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
- Ascending order priority queue
- 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