Last Updated on July 20, 2022 by Ria Pathak
Priority Queue:
Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.
Priority Queue Properties:
- In the priority queue, every element has priority assigned to it.
- The element with highest priority first.
- If two elements are having the same priority then they are served according to their order in the queue.
Implementation of Priority queue:
Priority queue is implemented in the following ways:
- Using Arrays.
- Using Linked List
- Using Heap data structure
- Using Binary Search Tree
1. Priority Queue using array:
Simple structure to implement a priority queue.
struct item {
int item;
int priority;
}
Enqueue(): This function is used to insert an element in the queue.
Dequeue(): This function is used to remove an element from the queue.
peek(): This function is used to get the highest priority element from the queue.
#include <bits/stdc++.h>
using namespace std;
struct item {
int value;
int priority;
};
item pr[100000];
int size = -1;
void enqueue(int value, int priority)
{
size++;
// Insert the element
pr[size].value = value;
pr[size].priority = priority;
}
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;
}
void dequeue()
{
int ind = peek();
for (int i = ind; i < size; i++) {
pr[i] = pr[i + 1];
}
size--;
}
int main()
{
enqueue(20, 2);
enqueue(14, 4);
enqueue(160, 4);
enqueue(120, 3);
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;
}
Time Complexity:
Enqueue: O(1)
Dequeue: O(N)
Peek: O(N)
2. Priority queue using Linked List:
In linked List, the elements are sorted in the descending order according to their priority, the element with the highest priority are added to the front of the priority queue that is formed using linked list.
Enqueue(): This function is used to insert an element in the queue.
Dequeue(): This function is used to remove an element from the queue.
peek(): This function is used to get the highest priority element from the queue.
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int data;
int priority;
struct node* next;
} Node;
Node* newNode(int d, int p)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
int peek(Node** head) { return (*head)->data; }
void pop(Node** head)
{
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
void push(Node** head, int d, int p)
{
Node* start = (*head);
Node* temp = newNode(d, p);
if ((*head)->priority > p) {
temp->next = *head;
(*head) = temp;
}
else {
while (start->next != NULL
&& start->next->priority < p) {
start = start->next;
}
temp->next = start->next;
start->next = temp;
}
}
int isEmpty(Node** head) { return (*head) == NULL; }
int main()
{
// Create a Priority Queue
// 10->20->30->40
Node* pq = newNode(20, 1);
push(&pq, 30, 2);
push(&pq, 40, 3);
push(&pq, 10, 0);
while (!isEmpty(&pq)) {
cout << " " << peek(&pq);
pop(&pq);
}
return 0;
}
Time Complexity:
Enqueue: O(N)
Dequeue: O(1)
Peek: O(1)
3. 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.
#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++;
}
}
}
H = [0]*50
size = -1
def parent(i) :
return (i - 1) // 2
def leftChild(i) :
return ((2 * i) + 1)
def rightChild(i) :
return ((2 * i) + 2)
def shiftUp(i) :
while (i > 0 and H[parent(i)] < H[i]) :
swap(parent(i), i)
i = parent(i)
def shiftDown(i) :
maxIndex = i
# Left Child
l = leftChild(i)
if (l <= size and H[l] > H[maxIndex]) :
maxIndex = l
# Right Child
r = rightChild(i)
if (r <= size and H[r] > H[maxIndex]) :
maxIndex = r
# If i not same as maxIndex
if (i != maxIndex) :
swap(i, maxIndex)
shiftDown(maxIndex)
def insert(p) :
global size
size = size + 1
H[size] = p
shiftUp(size)
def extractMax() :
global size
result = H[0]
H[0] = H[size]
size = size - 1
shiftDown(0)
return result
def changePriority(i,p) :
oldp = H[i]
H[i] = p
if (p > oldp) :
shiftUp(i)
else :
shiftDown(i)
def getMax() :
return H[0]
def Remove(i) :
H[i] = getMax() + 1
shiftUp(i)
# Extract the node
extractMax()
def swap(i, j) :
temp = H[i]
H[i] = H[j]
H[j] = temp
insert(55)
insert(20)
insert(14)
insert(12)
insert(31)
insert(7)
insert(11)
insert(13)
insert(7)
i = 0
# Priority queue before extracting max
print("Priority Queue : ", end = "")
while (i <= size) :
print(H[i], end = " ")
i += 1
print()
# Node with maximum priority
print("Node with maximum priority :" , extractMax())
# Priority queue after extracting max
print("Priority queue after extracting maximum : ", end = "")
j = 0
while (j <= size) :
print(H[j], end = " ")
j += 1
print()
# Change the priority of element
# present at index 2 to 49
changePriority(2, 49)
print("Priority queue after priority change : ", end = "")
k = 0
while (k <= size) :
print(H[k], end = " ")
k += 1
print()
# Remove element at index 3
Remove(3)
print("Priority queue after removing the element : ", end = "")
l = 0
while (l <= size) :
print(H[l], end = " ")
l += 1
Time Complexity:
Insertion: O(Log N)
Deletion: O(Log N)
Peek: O(1)
4. Using BST:
A self balancing tree like Red black tree, AVL Tree etc are used to implement the priority queue.
A BST takes O(log N) for both the operations i.e. insertion and deletion, Also we can find the top most element in the constant time O(1) by keeping the extra pointer which stores the highest priority element separately and update the pointer after every operation.
Applications of Priority queue:
- Priority queues are used to implement the stack.
- Priority queues are used to implement Dijkstra’s Algorithm.
- Also used in huffman code.
This article tried to discuss Priority Queue. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.