# What is a Priority Queue Data Structure? Implementation, Type & Many More

16 Aug 2024
Beginner
2.2K Views
Learn via Video Course & by Doing Hands-on Labs

## Priority Queue In DSA

Priority Queue in Data Structures is a special type of queue in which each element has a priority assigned to it. The operations performed are on a priority basis. Several ways to implement a priority queue include using an array, linked list, heap, or binary search tree. The best choice depends on the specific application.

In this DSA tutorial, we'll see the properties, types, representations, etc. of the priority queue. To get into a little more depth, refer to our Data Structures and Algorithms Course.

## What is a Priority Queue in Data Structures?

A priority queue is an abstract data type having all the characteristics of a normal queue except for the priority assigned to all the elements in it. Elements with higher priority values are retrieved before elements with lower priority values.

#### Priority Queue in Data Structure Example

Let's take a real-life example to understand this. Suppose in a single day we have to do a bundle of different tasks. In such a situation, we make a priority list as to which tasks are important to be finished today itself and which can be done afterward. This provides us with a proper direction to execute the plan for that specific day.

### Characteristics of a Priority Queue in Data Structures

• Every element in the queue has some priority assigned.
• All the queue elements must be comparable.
• The higher priority element is dequeued before the one with low priority.
• More than one element with the same priority is served as per the First Come First Serve Principle.

### Representation of a Priority Queue in Data Structures

Here, we'll represent the priority queue using a linked list. In the below three lists the data list contains the data elements, the Prior list contains the priority numbers of each data element available in the data list, and the Link list contains the address of the next node.

Before creating the queue, we must know the principle of assigning priority to the elements in the priority queue.

The priority assigned depends on the element itself. The element with the highest value is assigned the highest priority and the element with the lowest value is assigned the lowest priority. The reverse of this statement also holds. We can even assign the priority as per our requirements.

So now let's create the Priority Queue step by step.

1. In the list, the lower priority number is 1, whose data value is 243, so it will be inserted in the list as shown in the below diagram:
2. After inserting 243, priority number 2 has a higher priority, and data values associated with this priority are 232 and 111. So, this data will be inserted based on the FIFO principle; therefore 232 will be added first and then 111.
3. After inserting the elements of priority 2, the next higher priority number is 4, and data elements associated with 4 priority numbers are 333, 599, and 780. In this case, elements would be inserted based on the FIFO principle; therefore, 333 will be added first, then 599, and then 780.
4. After inserting the elements of priority 4, the next higher priority number is 5, and the value associated with priority 5 is 650, so it will be inserted at the end of the queue.4

## Types of Priority Queue in Data Structures

There are two types of priority queues:

1. Ascending Order Priority Queue: Here, the element with a lower priority value is given a higher priority in the priority list. For example, in the image below, we can see that 22 is the smallest among 22, 63, 76, 100, and 111; therefore, it will get the highest priority in a priority queue. So when we dequeue from this priority queue, 22 will be removed from the queue and dequeue returns 22.
2. Descending Order Priority Queue: Here, the element with a higher priority number is given as a higher priority in a priority list. For example, in the image below, we can see that 111 is the highest among 22, 63, 76, 100, and 111; therefore, it will get the highest priority in a priority queue.

## Operations on Priority Queue

We'll see the following operations on the priority queue in data structures.

Before moving forward, you need to be thorough with the concept of heap data structure. If you aren't, refer to our Heap in Data Structures tutorial.

### 1. Insertion: enqueue()

Algorithm for insertion into the priority queue(max-heap)

If there is no node,
create a newNode.
else (a node is already present)
insert the newNode at the end (last node from left to right.)

heapify the array

For insertion in the Min Heap, the above algorithm will get modified so that parentNode is always smaller than newNode.

According to the above algorithm, inserting an element into a priority queue (max-heap) is as follows:

1. Insert the new element at the end of the tree.
2. Heapify the tree.

### 2. Deletion: dequeue()

Algorithm for deletion into the priority queue(max-heap)

If nodeToBeDeleted is the leafNode
remove the node
Else swap nodeToBeDeleted with the lastLeafNode
remove noteToBeDeleted

heapify the array

For deletion in the Min Heap, the above algorithm will get modified so that both childNodes are smaller than currentNode.

According to the above algorithm, deleting an element from a priority queue (max-heap) is as follows:

1. Select the element to be deleted.

2. Swap it with the last element.

3. Remove the last element.

4. Heapify the tree.

### 3. Peek

Peek operation returns the maximum element from Max Heap or minimum element from Min Heap without deleting the node.

return rootNode

### 4. Extract-Max/Min from the Priority Queue

Extract-Max returns the node with maximum value after removing it from a Max Heap whereas Extract-Min returns the node with minimum value after removing it from Min Heap.

## Implementation of Priority Queue

Priority queue can be implemented using the following data structures:

### 1. Implement Priority Queue Using Array

For this, we will use an array of the following structure

#include <stdio.h>
#include  <limits.h>

#define MAX 100000

// Structure for the elements in the priority queue
typedef struct {
int value;
int priority;
} item;

// Priority queue structure
typedef struct {
item pr[MAX];
int size;
} queue;

// Function to insert a new element into priority queue
void enqueue(queue *q, int value, int priority) {
// Increase the size
q->size++;

// Insert the element
q->pr[q->size].value = value;
q->pr[q->size].priority = priority;
}

// Function to check the top element
int peek(queue *q) {
int highestPriority = INT_MIN;
int ind = -1;

// Check for the element with the highest priority
for (int i = 0; i <= q->size; i++) {
// If priority is same choose
// the element with the highest value
if ((highestPriority == q->pr[i].priority && ind > -1 && q->pr[ind].value < q->pr[i].value) ||
highestPriority < q->pr[i].priority) {
highestPriority = q->pr[i].priority;
ind = i;
}
}
// Return position of the element
return ind;
}

// Function to remove the element with the highest priority
void dequeue(queue *q) {
// Find the position of the element with highest priority
int ind = peek(q);

// Shift the elements one index before
for (int i = ind; i < q->size; i++) {
q->pr[i] = q->pr[i + 1];
}

// Decrease the size of the priority queue by one
q->size--;
}

int main() {
// Initialize the queue
queue q;
q.size = -1;

// Function Call to insert elements as per the priority
enqueue(&q, 14, 2);
enqueue(&q, 18, 4);
enqueue(&q, 16, 4);
enqueue(&q, 12, 3);

// Stores the top element at the moment
int ind = peek(&q);
printf("%d\n", q.pr[ind].value);

// Dequeue the top element
dequeue(&q);

// Check the top element
ind = peek(&q);
printf("%d\n", q.pr[ind].value);

// Dequeue the top element
dequeue(&q);

// Check the top element
ind = peek(&q);
printf("%d\n", q.pr[ind].value);

return 0;
}

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Structure for the elements in the priority queue
struct Item {
int value;
int priority;
};

// Class for priority queue
class Queue {
public:
// Store the elements of the priority queue
vector<Item> pr;

// Function to insert a new element into the priority queue
void enqueue(int value, int priority) {
Item newItem;
newItem.value = value;
newItem.priority = priority;
pr.push_back(newItem);
}

// Function to check the top element
int peek() {
int highestPriority = INT_MIN;
int ind = -1;

// Check for the element with the highest priority
for (int i = 0; i < pr.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 position of the element
return ind;
}

// Function to remove the element with the highest priority
void dequeue() {
// Find the position of the element with the highest priority
int ind = peek();

// Remove the element at that position
pr.erase(pr.begin() + ind);
}

// Main function to demonstrate the priority queue
void main() {
// Function Call to insert elements as per the priority
enqueue(14, 2);
enqueue(18, 4);
enqueue(16, 4);
enqueue(12, 3);

// Stores the top element at the moment
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;
}
};

// Entry point of the program
int main() {
Queue q;
q.main();
return 0;
}

using System;

class Item
{
public int Value { get; set; }
public int Priority { get; set; }
}

class Queue
{
// Store the elements of the priority queue
private Item[] pr = new Item[100000];

// Pointer to the last index
private int size = -1;

// Function to insert a new element into the priority queue
public void Enqueue(int value, int priority)
{
// Increase the size
size++;

// Insert the element
pr[size] = new Item();
pr[size].Value = value;
pr[size].Priority = priority;
}

// Function to check the top element
public int Peek()
{
int highestPriority = int.MinValue;
int ind = -1;

// Check for the element with the highest priority
for (int i = 0; i <= size; i++)
{
// If priority is the same, choose the element with the highest value
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 position of the element
return ind;
}

// Function to remove the element with the highest priority
public void Dequeue()
{
// Find the position of the element with the highest priority
int ind = Peek();

// Shift the elements one index before the position of the element with the highest priority
for (int i = ind; i < size; i++)
{
pr[i] = pr[i + 1];
}

// Decrease the size of the priority queue by one
size--;
}

public static void Main(string[] args)
{
Queue queue = new Queue();

// Function call to insert elements as per the priority
queue.Enqueue(14, 2);
queue.Enqueue(18, 4);
queue.Enqueue(16, 4);
queue.Enqueue(12, 3);

// Store the top element at the moment
int ind = queue.Peek();
Console.WriteLine(queue.pr[ind].Value);

// Dequeue the top element
queue.Dequeue();

// Check the top element
ind = queue.Peek();
Console.WriteLine(queue.pr[ind].Value);

// Dequeue the top element
queue.Dequeue();

// Check the top element
ind = queue.Peek();
Console.WriteLine(queue.pr[ind].Value);
}
}

import sys

# Structure for the elements in the priority queue
class item :
value = 0
priority = 0

class queue :

# Store the element of a priority queue
pr = [None] * (100000)

# Pointer to the last index
size = -1

# Function to insert a new element into priority queue
@staticmethod
def enqueue( value, priority) :

# Increase the size
queue.size += 1

# Insert the element
queue.pr[queue.size] = item()
queue.pr[queue.size].value = value
queue.pr[queue.size].priority = priority

# Function to check the top element
@staticmethod
def peek() :
highestPriority = -sys.maxsize
ind = -1

# Check for the element with highest priority
i = 0
while (i <= queue.size) :

# If priority is same choose
# the element with the highest value
if (highestPriority == queue.pr[i].priority and ind > -1 and queue.pr[ind].value < queue.pr[i].value) :
highestPriority = queue.pr[i].priority
ind = i
elif(highestPriority < queue.pr[i].priority) :
highestPriority = queue.pr[i].priority
ind = i
i += 1

# Return position of the element
return ind

# Function to remove the element with the highest priority
@staticmethod
def dequeue() :

# Find the position of the element with highest priority
ind = queue.peek()

# Shift the element one index before
# from the position of the element with highest priority is found
i = ind
while (i < queue.size) :
queue.pr[i] = queue.pr[i + 1]
i += 1

# Decrease the size of the priority queue by one
queue.size -= 1
@staticmethod
def main( args) :

# Function Call to insert elements as per the priority
queue.enqueue(14, 2)
queue.enqueue(18, 4)
queue.enqueue(16, 4)
queue.enqueue(12, 3)

# Stores the top element at the moment
ind = queue.peek()
print(queue.pr[ind].value)

# Dequeue the top element
queue.dequeue()

# Check the top element
ind = queue.peek()
print(queue.pr[ind].value)

# Dequeue the top element
queue.dequeue()

# Check the top element
ind = queue.peek()
print(queue.pr[ind].value)

if __name__=="__main__":
queue.main([])

import java.util.*;

// Structure for the elements in the priority queue
class Item {
public int value;
public int priority;
}

class Queue {
// Store the element of a priority queue
static Item[] pr = new Item[100000];

// Pointer to the last index
static int size = -1;

// Function to insert a new element into priority queue
static void enqueue(int value, int priority) {
// Increase the size
size++;

// Insert the element
pr[size] = new Item();
pr[size].value = value;
pr[size].priority = priority;
}

// Function to check the top element
static int peek() {
int highestPriority = Integer.MIN_VALUE;
int ind = -1;

// Check for the element with highest priority
for (int i = 0; i <= size; i++) {
// If priority is same, choose the element with the highest value
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 position of the element
return ind;
}

// Function to remove the element with the highest priority
static void dequeue() {
// Find the position of the element with highest priority
int ind = peek();

if (ind != -1) {
// Shift the element one index before from the position of the element with highest priority
for (int i = ind; i < size; i++) {
pr[i] = pr[i + 1];
}

// Decrease the size of the priority queue by one
size--;
}
}

public static void main(String[] args) {
// Function Call to insert elements as per the priority
enqueue(14, 2);
enqueue(18, 4);
enqueue(16, 4);
enqueue(12, 3);

// Stores the top element at the moment
int ind = peek();
if (ind != -1) {
System.out.println(pr[ind].value);
}

// Dequeue the top element
dequeue();

// Check the top element
ind = peek();
if (ind != -1) {
System.out.println(pr[ind].value);
}

// Dequeue the top element
dequeue();

// Check the top element
ind = peek();
if (ind != -1) {
System.out.println(pr[ind].value);
}
}
}

class Item {
constructor(value, priority) {
this.value = value;
this.priority = priority;
}
}

class Queue {
constructor() {
this.pr = [];
this.size = -1;
}

enqueue(value, priority) {
this.size++;
this.pr[this.size] = new Item(value, priority);
}

peek() {
let highestPriority = -Infinity;
let ind = -1;

for (let i = 0; i <= this.size; i++) {
if (highestPriority === this.pr[i].priority) {
if (ind > -1 && this.pr[ind].value < this.pr[i].value) {
highestPriority = this.pr[i].priority;
ind = i;
}
} else if (highestPriority < this.pr[i].priority) {
highestPriority = this.pr[i].priority;
ind = i;
}
}

return ind;
}

dequeue() {
const ind = this.peek();

for (let i = ind; i < this.size; i++) {
this.pr[i] = this.pr[i + 1];
}

this.size--;
}

static main() {
const queue = new Queue();

queue.enqueue(14, 2);
queue.enqueue(18, 4);
queue.enqueue(16, 4);
queue.enqueue(12, 3);

let ind = queue.peek();
console.log(queue.pr[ind].value);

queue.dequeue();

ind = queue.peek();
console.log(queue.pr[ind].value);

queue.dequeue();

ind = queue.peek();
console.log(queue.pr[ind].value);
}
}

// Run the main function
Queue.main();

We have executed the above code in all our compilers for example Python Compiler, Java Compiler, and C++ Compiler

#### Output

18
16
12

Read More: Arrays in Data Structures

### 2) Implement Priority Queue Using Linked List

In a Linked List implementation, the entries are sorted in descending order based on their priority. The highest priority element is always added to the front of the priority queue.

#include <stdio.h>
#include <stdlib.h>

// Node structure for the priority queue
typedef struct PriorityQueueNode {
int data;
int priority;
struct PriorityQueueNode* next;
} PriorityQueueNode;

// Priority Queue structure
typedef struct PriorityQueue {
PriorityQueueNode* front;
} PriorityQueue;

// Function to create a new node
PriorityQueueNode* createNode(int value, int priority) {
PriorityQueueNode* newNode = (PriorityQueueNode*)malloc(sizeof(PriorityQueueNode));
newNode->data = value;
newNode->priority = priority;
newNode->next = NULL;
return newNode;
}

// Function to check if the queue is empty
int isEmpty(PriorityQueue* pq) {
return (pq->front == NULL);
}

// Function to push a node into the priority queue
void push(PriorityQueue* pq, int value, int priority) {
PriorityQueueNode* newNode = createNode(value, priority);

if (isEmpty(pq) || pq->front->priority > priority) {
newNode->next = pq->front;
pq->front = newNode;
} else {
PriorityQueueNode* temp = pq->front;
while (temp->next != NULL && temp->next->priority <= priority) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}

// Function to pop the front node from the priority queue
void pop(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Queue is empty, nothing to pop.\n");
return;
} else {
PriorityQueueNode* temp = pq->front;
pq->front = pq->front->next;
free(temp);
}
}

// Function to get the data at the front of the queue
int peek(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Queue is empty.\n");
return -1;
} else {
return pq->front->data;
}
}

// Function to traverse and print the priority queue
void traverse(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Queue is empty.\n");
} else {
PriorityQueueNode* temp = pq->front;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}

int main() {
PriorityQueue pq;
pq.front = NULL;

push(&pq, 14, 1);
push(&pq, 18, 2);
push(&pq, 16, 3);
push(&pq, 12, 0);

traverse(&pq);

pop(&pq);
traverse(&pq);

return 0;
}

#include <iostream>
using namespace std;

class PriorityQueueNode {
public:
int data;
int priority;
PriorityQueueNode* next;

PriorityQueueNode(int value, int pr) {
data = value;
priority = pr;
next = nullptr;
}
};

class PriorityQueue {
private:
PriorityQueueNode* front;

public:
PriorityQueue() {
front = nullptr;
}

bool isEmpty() {
return front == nullptr;
}

void push(int value, int priority) {
PriorityQueueNode* newNode = new PriorityQueueNode(value, priority);

if (isEmpty() || front->priority > priority) {
newNode->next = front;
front = newNode;
} else {
PriorityQueueNode* temp = front;
while (temp->next != nullptr && temp->next->priority <= priority) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}

void pop() {
if (isEmpty()) {
cout << "Queue is Empty!" << endl;
} else {
PriorityQueueNode* temp = front;
front = front->next;
delete temp;
}
}

int peek() {
if (isEmpty()) {
cout << "Queue is Empty!" << endl;
return -1; // Return -1 if the queue is empty
} else {
return front->data;
}
}

void traverse() {
if (isEmpty()) {
cout << "Queue is Empty!" << endl;
} else {
PriorityQueueNode* temp = front;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
}
};

int main() {
PriorityQueue pq;
pq.push(14, 1);
pq.push(18, 2);
pq.push(16, 3);
pq.push(12, 0);

pq.traverse(); // Output: 12 14 18 16

pq.pop();      // Removes the element with the highest priority (lowest priority number)

pq.traverse(); // Output: 14 18 16

return 0;
}

using System;

class PriorityQueueNode
{
public int Data { get; set; }
public int Priority { get; set; }
public PriorityQueueNode Next { get; set; }

public PriorityQueueNode(int value, int pr)
{
Data = value;
Priority = pr;
Next = null;
}
}

class PriorityQueue
{
private PriorityQueueNode front;

public PriorityQueue()
{
front = null;
}

public bool IsEmpty()
{
return front == null;
}

public void Push(int value, int priority)
{
PriorityQueueNode newNode = new PriorityQueueNode(value, priority);

if (IsEmpty())
{
front = newNode;
}
else
{
if (front.Priority > priority)
{
newNode.Next = front;
front = newNode;
}
else
{
PriorityQueueNode temp = front;
while (temp.Next != null && temp.Next.Priority <= priority)
{
temp = temp.Next;
}
newNode.Next = temp.Next;
temp.Next = newNode;
}
}
}

public void Pop()
{
if (!IsEmpty())
{
front = front.Next;
}
}

public int Peek()
{
return IsEmpty() ? -1 : front.Data;
}

public void Traverse()
{
if (IsEmpty())
{
Console.WriteLine("Queue is Empty!");
}
else
{
PriorityQueueNode temp = front;
while (temp != null)
{
Console.Write(temp.Data + " ");
temp = temp.Next;
}
}
}
}

class Program
{
static void Main()
{
PriorityQueue pq = new PriorityQueue();
pq.Push(14, 1);
pq.Push(18, 2);
pq.Push(16, 3);
pq.Push(12, 0);

pq.Traverse(); // Output: 12 14 18 16

pq.Pop();

Console.WriteLine();
pq.Traverse(); // Output after pop: 14 18 16
}
}

class PriorityQueueNode:
def __init__(self, value, priority):
self.data = value
self.priority = priority
self.next = None

class PriorityQueue:
def __init__(self):
self.front = None

def is_empty(self):
return self.front is None

def push(self, value, priority):
new_node = PriorityQueueNode(value, priority)

if self.is_empty() or self.front.priority > priority:
new_node.next = self.front
self.front = new_node
else:
temp = self.front
while temp.next and temp.next.priority <= priority:
temp = temp.next
new_node.next = temp.next
temp.next = new_node

def pop(self):
if self.is_empty():
return
else:
self.front = self.front.next

def peek(self):
if self.is_empty():
return None
else:
return self.front.data

def traverse(self):
if self.is_empty():
return "Queue is Empty!"
else:
temp = self.front
result = ''
while temp:
result += str(temp.data) + " "
temp = temp.next
return result.strip()

# Example usage
pq = PriorityQueue()
pq.push(14, 1)
pq.push(18, 2)
pq.push(16, 3)
pq.push(12, 0)

print(pq.traverse())  # Output: 12 14 18 16

pq.pop()
print(pq.traverse())  # Output: 14 18 16

class PriorityQueueNode {
int data;
int priority;
PriorityQueueNode next;

public PriorityQueueNode(int value, int pr) {
this.data = value;
this.priority = pr;
this.next = null;
}
}

class PriorityQueue {
private PriorityQueueNode front;

public PriorityQueue() {
this.front = null;
}

public boolean isEmpty() {
return front == null;
}

public void push(int value, int priority) {
PriorityQueueNode newNode = new PriorityQueueNode(value, priority);

if (isEmpty() || front.priority > priority) {
newNode.next = front;
front = newNode;
} else {
PriorityQueueNode temp = front;
while (temp.next != null && temp.next.priority <= priority) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
}
}

public void pop() {
if (!isEmpty()) {
front = front.next;
}
}

public int peek() {
if (!isEmpty()) {
return front.data;
}
return -1; // Return -1 if queue is empty
}

public void traverse() {
if (isEmpty()) {
System.out.println("Queue is Empty!");
} else {
PriorityQueueNode temp = front;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
}
}

public class Main {
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue();
pq.push(14, 1);
pq.push(18, 2);
pq.push(16, 3);
pq.push(12, 0);

pq.traverse();

pq.pop();
pq.traverse();
}
}

class PriorityQueueNode {
constructor(value, priority) {
this.data = value;
this.priority = priority;
this.next = null;
}
}

class PriorityQueue {
constructor() {
this.front = null;
}

isEmpty() {
return this.front === null;
}

push(value, priority) {
const newNode = new PriorityQueueNode(value, priority);

if (this.isEmpty() || this.front.priority > priority) {
newNode.next = this.front;
this.front = newNode;
} else {
let temp = this.front;
while (temp.next && temp.next.priority <= priority) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
}
}

pop() {
if (this.isEmpty()) {
return;
} else {
this.front = this.front.next;
}
}

peek() {
if (this.isEmpty()) {
return null;
} else {
return this.front.data;
}
}

traverse() {
if (this.isEmpty()) {
return "Queue is Empty!";
} else {
let temp = this.front;
let result = '';
while (temp) {
result += temp.data + " ";
temp = temp.next;
}
return result.trim();
}
}
}

// Example usage
const pq = new PriorityQueue();
pq.push(14, 1);
pq.push(18, 2);
pq.push(16, 3);
pq.push(12, 0);

console.log(pq.traverse());  // Output: 12 14 18 16

pq.pop();
console.log(pq.traverse());  // Output: 14 18 16

The above code for the linked list implementation of the priority queue is implemented in Python, C++Java, and some other compilers too.

12 14 18 16
14 18 16

### 3. Implement Priority Queue Using HeapsCC++C#PythonJavaJavascript #include <stdio.h> void swap(int *a, int *b) { int temp = *b; *b = *a; *a = temp; } void heapify(int hT[], int size, int i) { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < size && hT[l] > hT[largest]) largest = l; if (r < size && hT[r] > hT[largest]) largest = r; if (largest != i) { swap(&hT[i], &hT[largest]); heapify(hT, size, largest); } } void insert(int hT[], int *size, int newNum) { hT[*size] = newNum; (*size)++; for (int i = (*size) / 2 - 1; i >= 0; i--) heapify(hT, *size, i); } void deleteNode(int hT[], int *size, int num) { int i; for (i = 0; i < *size; i++) { if (num == hT[i]) break; } swap(&hT[i], &hT[*size - 1]); (*size)--; for (int i = (*size) / 2 - 1; i >= 0; i--) heapify(hT, *size, i); } void printArray(int hT[], int size) { for (int i = 0; i < size; i++) printf("%d ", hT[i]); printf("\n"); } int main() { int heapTree[10]; int size = 0; insert(heapTree, &size, 3); insert(heapTree, &size, 4); insert(heapTree, &size, 9); insert(heapTree, &size, 5); insert(heapTree, &size, 2); printf("Max-Heap array: "); printArray(heapTree, size); deleteNode(heapTree, &size, 4); printf("After deleting an element: "); printArray(heapTree, size); return 0; } #include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to swap two elements void swap(int &a, int &b) { int temp = b; b = a; a = temp; } // Function to heapify the tree void heapify(vector<int> &hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < size && hT[l] > hT[largest]) largest = l; if (r < size && hT[r] > hT[largest]) largest = r; if (largest != i) { swap(hT[i], hT[largest]); heapify(hT, largest); } } // Function to insert an element into the tree void insert(vector<int> &hT, int newNum) { int size = hT.size(); hT.push_back(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } // Function to delete an element from the tree void deleteNode(vector<int> &hT, int num) { int size = hT.size(); int i; for (i = 0; i < size; i++) { if (num == hT[i]) break; } swap(hT[i], hT[size - 1]); hT.pop_back(); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } // Function to print the heap array void printArray(vector<int> &hT) { for (int i = 0; i < hT.size(); i++) { cout << hT[i] << " "; } cout << endl; } // Driver code int main() { vector<int> heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); return 0; } using System; using System.Collections.Generic; class MaxHeap { public List<int> heapTree = new List<int>(); private void Swap(int i, int j) { int temp = heapTree[i]; heapTree[i] = heapTree[j]; heapTree[j] = temp; } // Function to heapify the tree private void Heapify(int i) { int size = heapTree.Count; int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < size && heapTree[left] > heapTree[largest]) { largest = left; } if (right < size && heapTree[right] > heapTree[largest]) { largest = right; } if (largest != i) { Swap(i, largest); Heapify(largest); } } // Function to insert an element into the tree public void Insert(int newNum) { int size = heapTree.Count; heapTree.Add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { Heapify(i); } } // Function to delete an element from the tree public void DeleteNode(int num) { int size = heapTree.Count; int i; for (i = 0; i < size; i++) { if (num == heapTree[i]) { break; } } Swap(i, size - 1); heapTree.RemoveAt(size - 1); for (int j = size / 2 - 1; j >= 0; j--) { Heapify(j); } } // Print the tree public void PrintArray() { foreach (int item in heapTree) { Console.Write(item + " "); } Console.WriteLine(); } } class Program { static void Main(string[] args) { MaxHeap maxHeap = new MaxHeap(); maxHeap.Insert(3); maxHeap.Insert(4); maxHeap.Insert(9); maxHeap.Insert(5); maxHeap.Insert(2); Console.Write("Max-Heap array: "); maxHeap.PrintArray(); maxHeap.DeleteNode(4); Console.Write("After deleting an element: "); maxHeap.PrintArray(); } } def swap(a, b): temp = b b = a a = temp # Function to heapify the tree def heapify(hT, i): size = len(hT) # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < size and hT[l] > hT[largest]: largest = l if r < size and hT[r] > hT[largest]: largest = r # Swap and continue heapifying if root is not largest if largest != i: hT[i], hT[largest] = hT[largest], hT[i] heapify(hT, largest) # Function to insert an element into the tree def insert(hT, newNum): size = len(hT) if size == 0: hT.append(newNum) else: hT.append(newNum) for i in range(size//2-1, -1, -1): heapify(hT, i) # Function to delete an element from the tree def deleteNode(hT, num): size = len(hT) i = 0 for i in range(size): if num == hT[i]: break hT[i], hT[size-1] = hT[size-1], hT[i] hT.pop() for i in range(size//2-1, -1, -1): heapify(hT, i) # Print the tree def printArray(hT): for i in range(len(hT)): print(hT[i], end=" ") print() # Driver code if __name__ == "__main__": heapTree = [] insert(heapTree, 3) insert(heapTree, 4) insert(heapTree, 9) insert(heapTree, 5) insert(heapTree, 2) print("Max-Heap array:", end=" ") printArray(heapTree) deleteNode(heapTree, 4) print("After deleting an element:", end=" ") printArray(heapTree) import java.util.ArrayList; class MaxHeap { private ArrayList<Integer> heapTree = new ArrayList<>(); // Function to swap elements private void swap(int a, int b) { int temp = heapTree.get(b); heapTree.set(b, heapTree.get(a)); heapTree.set(a, temp); } // Function to heapify the tree private void heapify(int i) { int size = heapTree.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < size && heapTree.get(l) > heapTree.get(largest)) { largest = l; } if (r < size && heapTree.get(r) > heapTree.get(largest)) { largest = r; } if (largest != i) { swap(i, largest); heapify(largest); } } // Function to insert an element into the tree public void insert(int newNum) { heapTree.add(newNum); int size = heapTree.size(); for (int i = size / 2 - 1; i >= 0; i--) { heapify(i); } } // Function to delete an element from the tree public void deleteNode(int num) { int size = heapTree.size(); int i; for (i = 0; i < size; i++) { if (num == heapTree.get(i)) { break; } } swap(i, size - 1); heapTree.remove(size - 1); for (int j = size / 2 - 1; j >= 0; j--) { heapify(j); } } // Function to print the tree public void printArray() { for (int i = 0; i < heapTree.size(); i++) { System.out.print(heapTree.get(i) + " "); } System.out.println(); } public static void main(String[] args) { MaxHeap heap = new MaxHeap(); heap.insert(3); heap.insert(4); heap.insert(9); heap.insert(5); heap.insert(2); System.out.print("Max-Heap array: "); heap.printArray(); heap.deleteNode(4); System.out.print("After deleting an element: "); heap.printArray(); } } function swap(arr, a, b) { let temp = arr[b]; arr[b] = arr[a]; arr[a] = temp; } // Function to heapify the tree function heapify(hT, i) { const size = hT.length; let largest = i; const l = 2 * i + 1; const r = 2 * i + 2; if (l < size && hT[l] > hT[largest]) { largest = l; } if (r < size && hT[r] > hT[largest]) { largest = r; } // Swap and continue heapifying if root is not largest if (largest !== i) { swap(hT, i, largest); heapify(hT, largest); } } // Function to insert an element into the tree function insert(hT, newNum) { hT.push(newNum); const size = hT.length; for (let i = Math.floor(size / 2) - 1; i >= 0; i--) { heapify(hT, i); } } // Function to delete an element from the tree function deleteNode(hT, num) { const size = hT.length; let i; for (i = 0; i < size; i++) { if (num === hT[i]) { break; } } swap(hT, i, size - 1); hT.pop(); for (let i = Math.floor(hT.length / 2) - 1; i >= 0; i--) { heapify(hT, i); } } // Function to print the tree function printArray(hT) { console.log(hT.join(" ")); } // Driver code const heapTree = []; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); console.log("Max-Heap array: "); printArray(heapTree); deleteNode(heapTree, 4); console.log("After deleting an element: "); printArray(heapTree);

#### Output

Max-Heap array: 9 5 3 4 2
After deleting an element: 9 5 3 2

### 4. Implement Priority Queue Using Binary Search Tree

A Self-Balancing Binary Search Tree like an AVL Tree, Red-Black Tree, etc. can be used to implement a priority queue.

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a tree node
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new TreeNode
struct TreeNode* createNode(int val) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a value into the BST
struct TreeNode* insert(struct TreeNode* node, int val) {
if (node == NULL) {
return createNode(val);
}
if (val < node->val) {
node->left = insert(node->left, val);
} else {
node->right = insert(node->right, val);
}
return node;
}

// Function to find the maximum value in a BST
struct TreeNode* findMax(struct TreeNode* node) {
while (node->right != NULL) {
node = node->right;
}
return node;
}

// Function to delete a node from the BST and return the new root
struct TreeNode* deleteNode(struct TreeNode* node, int val) {
if (node == NULL) {
return NULL;
}
if (val < node->val) {
node->left = deleteNode(node->left, val);
} else if (val > node->val) {
node->right = deleteNode(node->right, val);
} else {
// Node with only one child or no child
if (node->left == NULL) {
struct TreeNode* temp = node->right;
free(node);
return temp;
} else if (node->right == NULL) {
struct TreeNode* temp = node->left;
free(node);
return temp;
}

// Node with two children: Get the inorder predecessor (max in left subtree)
struct TreeNode* temp = findMax(node->left);
node->val = temp->val;
node->left = deleteNode(node->left, temp->val);
}
return node;
}

// Function to delete the maximum value in the BST
int deleteMax(struct TreeNode** root) {
if (*root == NULL) {
return -1;
}
struct TreeNode* maxNode = findMax(*root);
int maxVal = maxNode->val;
*root = deleteNode(*root, maxVal);
return maxVal;
}

// Function to check if the BST is empty
int isEmpty(struct TreeNode* root) {
return root == NULL;
}

// Example usage
int main() {
struct TreeNode* pq = NULL;
pq = insert(pq, 10);
pq = insert(pq, 20);
pq = insert(pq, 5);
pq = insert(pq, 15);

while (!isEmpty(pq)) {
printf("%d\n", deleteMax(&pq));
}

return 0;
}

#include <iostream>

class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;

TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

class PriorityQueueBST {
private:
TreeNode* root;

TreeNode* insert(TreeNode* node, int val) {
if (!node) {
return new TreeNode(val);
}
if (val < node->val) {
node->left = insert(node->left, val);
} else {
node->right = insert(node->right, val);
}
return node;
}

TreeNode* findMax(TreeNode* node) {
while (node->right) {
node = node->right;
}
return node;
}

TreeNode* deleteNode(TreeNode* node, int val) {
if (!node) {
return nullptr;
}
if (val < node->val) {
node->left = deleteNode(node->left, val);
} else if (val > node->val) {
node->right = deleteNode(node->right, val);
} else {
if (!node->left) {
return node->right;
}
if (!node->right) {
return node->left;
}
TreeNode* temp = findMax(node->left);
node->val = temp->val;
node->left = deleteNode(node->left, temp->val);
}
return node;
}

public:
PriorityQueueBST() : root(nullptr) {}

void insert(int val) {
root = insert(root, val);
}

int deleteMax() {
if (!root) {
return -1; // Assuming -1 as an indication of an empty tree.
}
TreeNode* maxNode = findMax(root);
int maxVal = maxNode->val;
root = deleteNode(root, maxVal);
return maxVal;
}

bool isEmpty() {
return root == nullptr;
}
};

// Example usage:
int main() {
PriorityQueueBST pq;
pq.insert(10);
pq.insert(20);
pq.insert(5);
pq.insert(15);

while (!pq.isEmpty()) {
std::cout << pq.deleteMax() << std::endl;
}

return 0;
}

using System;

class TreeNode
{
public int Val;
public TreeNode Left;
public TreeNode Right;

public TreeNode(int val)
{
Val = val;
Left = null;
Right = null;
}
}

class PriorityQueueBST
{
private TreeNode root;

public PriorityQueueBST()
{
root = null;
}

public void Insert(int val)
{
root = InsertHelper(root, val);
}

private TreeNode InsertHelper(TreeNode node, int val)
{
if (node == null)
return new TreeNode(val);

if (val < node.Val)
node.Left = InsertHelper(node.Left, val);
else
node.Right = InsertHelper(node.Right, val);

return node;
}

public int? Delete()
{
if (root == null)
return null;

int maxVal = FindMax(root).Val;
root = DeleteNode(root, maxVal);
return maxVal;
}

private TreeNode FindMax(TreeNode node)
{
while (node.Right != null)
node = node.Right;
return node;
}

private TreeNode DeleteNode(TreeNode node, int val)
{
if (node == null)
return null;

if (val < node.Val)
node.Left = DeleteNode(node.Left, val);
else if (val > node.Val)
node.Right = DeleteNode(node.Right, val);
else
{
if (node.Left == null)
return node.Right;
if (node.Right == null)
return node.Left;

TreeNode temp = FindMax(node.Left);
node.Val = temp.Val;
node.Left = DeleteNode(node.Left, temp.Val);
}

return node;
}

public bool IsEmpty()
{
return root == null;
}
}

// Example usage
class Program
{
static void Main()
{
PriorityQueueBST pq = new PriorityQueueBST();
pq.Insert(10);
pq.Insert(20);
pq.Insert(5);
pq.Insert(15);

while (!pq.IsEmpty())
{
Console.WriteLine(pq.Delete());
}
}
}

class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

class PriorityQueueBST:
def __init__(self):
self.root = None

def insert(self, val):
def helper(node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = helper(node.left, val)
else:
node.right = helper(node.right, val)
return node

self.root = helper(self.root, val)

def delete(self):
def find_max(node):
while node.right:
node = node.right
return node

def delete_node(node, val):
if not node:
return None
if val < node.val:
node.left = delete_node(node.left, val)
elif val > node.val:
node.right = delete_node(node.right, val)
else:
if not node.left:
return node.right
if not node.right:
return node.left
temp = find_max(node.left)
node.val = temp.val
node.left = delete_node(node.left, temp.val)
return node

if not self.root:
return None
max_val = find_max(self.root).val
self.root = delete_node(self.root, max_val)
return max_val

def is_empty(self):
return self.root is None

# Example usage:
pq = PriorityQueueBST()
pq.insert(10)
pq.insert(20)
pq.insert(5)
pq.insert(15)

while not pq.is_empty():
print(pq.delete())

class TreeNode {
int val;
TreeNode left, right;

TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}

class PriorityQueueBST {
private TreeNode root;

PriorityQueueBST() {
this.root = null;
}

public void insert(int val) {
this.root = insertHelper(this.root, val);
}

private TreeNode insertHelper(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insertHelper(node.left, val);
} else {
node.right = insertHelper(node.right, val);
}
return node;
}

public int delete() {
if (this.root == null) {
throw new IllegalStateException("Priority queue is empty");
}

int maxVal = findMax(this.root).val;
this.root = deleteNode(this.root, maxVal);
return maxVal;
}

private TreeNode findMax(TreeNode node) {
while (node.right != null) {
node = node.right;
}
return node;
}

private TreeNode deleteNode(TreeNode node, int val) {
if (node == null) {
return null;
}
if (val < node.val) {
node.left = deleteNode(node.left, val);
} else if (val > node.val) {
node.right = deleteNode(node.right, val);
} else {
if (node.left == null) {
return node.right;
}
if (node.right == null) {
return node.left;
}

TreeNode temp = findMax(node.left);
node.val = temp.val;
node.left = deleteNode(node.left, temp.val);
}
return node;
}

public boolean isEmpty() {
return this.root == null;
}

// Example usage
public static void main(String[] args) {
PriorityQueueBST pq = new PriorityQueueBST();
pq.insert(10);
pq.insert(20);
pq.insert(5);
pq.insert(15);

while (!pq.isEmpty()) {
System.out.println(pq.delete());
}
}
}

class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}

class PriorityQueueBST {
constructor() {
this.root = null;
}

insert(val) {
const helper = (node, val) => {
if (!node) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = helper(node.left, val);
} else {
node.right = helper(node.right, val);
}
return node;
};

this.root = helper(this.root, val);
}

delete() {
const findMax = (node) => {
while (node.right) {
node = node.right;
}
return node;
};

const deleteNode = (node, val) => {
if (!node) {
return null;
}
if (val < node.val) {
node.left = deleteNode(node.left, val);
} else if (val > node.val) {
node.right = deleteNode(node.right, val);
} else {
if (!node.left) {
return node.right;
}
if (!node.right) {
return node.left;
}
const temp = findMax(node.left);
node.val = temp.val;
node.left = deleteNode(node.left, temp.val);
}
return node;
};

if (!this.root) {
return null;
}
const maxVal = findMax(this.root).val;
this.root = deleteNode(this.root, maxVal);
return maxVal;
}

isEmpty() {
return this.root === null;
}
}
// Example usage:
const pq = new PriorityQueueBST();
pq.insert(10);
pq.insert(20);
pq.insert(5);
pq.insert(15);

while (!pq.isEmpty()) {
console.log(pq.delete());
}

#### Output

20
15
10
5

Read More: Binary Search Tree in Data Structures

## Applications of Priority Queue

• CPU Scheduling
• Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc.
• Stack Implementation
• All queue applications where priority is involved.
• Data compression in Huffman code
• for load balancing and interrupt handling in an operating system
• Finding Kth's largest/smallest element

• Efficient Operations: Inserting elements into a Priority Queue and removing them based on their priority can be done efficiently. This is beneficial in applications that require frequent insertions and deletions.
• Flexibility: A Priority Queue can be implemented with arrays, linked lists, or heaps to suit different scenarios and applications.
• Quick access to elements: As the elements in a priority queue are ordered according to priority, one can easily retrieve the highest priority element without searching the entire queue.
• Applicability in Algorithms: Priority Queues are crucial to the efficient functioning of several algorithms, including sorting algorithms like Heap Sort or graph algorithms like Dijkstra's Algorithm.

• Complexity: Priority queues can be more complex to implement and maintain unlike arrays or linked lists.
• Priority Conflicts: Determining the priority of elements can be challenging, and conflicts may arise when two elements have the same priority.
• Performance Overhead: Updating the priority of elements in the queue can be slow, especially for larger queues, leading to performance overhead.
• 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.
• Priority Inversion: Priority inversion can occur when a high-priority task is blocked by a lower-priority task, leading to suboptimal performance.
• 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.

## Summary

So, here we saw every aspect of a priority queue in data structures. You might have got at least some idea regarding priority queues and their applications. I know it's quite difficult to understand the whole topic in a single go. Therefore, refer to it again and again till you get thorough with the queue in data structures. To test your knowledge of priority queues, enroll in our Best Data Structures And Algorithms Course.

## FAQs

### Q1. What is priority queue in data structure?

Priority Queue in data structures is a special type of queue in which each element has a priority assigned to it.

### Q2. What is priority queue order?

The order of elements in a priority queue depends on the priority assigned to each element.

### Q3. What is a priority queue of lists?

A priority queue of lists is a data structure that combines the properties of a priority queue and a list. In this structure, each element in the priority queue is a list, and elements are processed based on their priority within these lists.

Share Article

### Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 ASP.NET Core Certification Training Sep 15 SAT, SUN Filling Fast09:30AM to 11:30AM (IST) Advanced Full-Stack .NET Developer Certification Training Sep 15 SAT, SUN Filling Fast09:30AM to 11:30AM (IST) .NET Solution Architect Certification Training Sep 22 SAT, SUN Filling Fast07:00AM to 09:00AM (IST) Software Architecture and Design Training Sep 22 SAT, SUN Filling Fast07:00AM to 09:00AM (IST) Advanced Full-Stack .NET Developer Certification Training Sep 29 SAT, SUN Filling Fast08:30PM to 10:30PM (IST) ASP.NET Core Certification Training Sep 29 SAT, SUN Filling Fast08:30PM to 10:30PM (IST)

Can't find convenient schedule? Let us know