Priority Queue in Data Structures

03 May 2024

Beginner

220 Views

60 min read

Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course

Free Course Self Paced Courses Hands-On Labs Interview Q&A

Data Structures Priority Queue: An Overview

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.

Representation of a Priority Queue in Data Structures

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.

Representation of a Priority Queue in Data Structures

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

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:
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.
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.
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

Representation of a Priority Queue in Data Structures

Types of Priority Queue in Data Structures

There are two types of priority queues:

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.
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:

Insert the new element at the end of the tree.
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:

Select the element to be deleted.
Swap it with the last element.
Remove the last element.
Heapify the tree.

3. Peek

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

Syntax to perform peek operation on both, max and min heap

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


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();

	// Shift the element one index before
	// from the position of the element
	// with highest priority is found
	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();

	System.out.println(pr[ind].value);

	// Dequeue the top element
	dequeue();

	// Check the top element
	ind = peek();
	System.out.println(pr[ind].value);

	// Dequeue the top element
	dequeue();

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


 #include 
using namespace std;

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

// Store the element of a priority queue
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;

	// 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
void dequeue()
{
	// Find the position of the element
	// with highest priority
	int ind = peek();

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

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

// Driver Code
int 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;

	return 0;
}

We have executed the above code in all our three compilers, 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.


class PriorityQueueNode:
  
  def __init__(self, value, pr):
      
    self.data = value
    self.priority = pr
    self.next = None
  
class PriorityQueue:
  
  def __init__(self):
    
    self.front = None
    
  def isEmpty(self):
    
    return True if self.front == None else False
  
  def push(self, value, priority):
    
    if self.isEmpty() == True:
      
      self.front = PriorityQueueNode(value, priority)
      return 1
      
    else:
      
      if self.front.priority > priority:
        
        newNode = PriorityQueueNode(value, priority)
        
        newNode.next = self.front
        
        self.front = newNode
        
        return 1
        
      else:
        
        temp = self.front
        
        while temp.next:
          
          if priority <= temp.next.priority:
            break
          
          temp = temp.next
        
        newNode = PriorityQueueNode(value, priority)
        newNode.next = temp.next
        temp.next = newNode
        
        return 1
  
  def pop(self):
    
    if self.isEmpty() == True:
      return
    
    else:
      
      self.front = self.front.next
      return 1
      
  def peek(self):
    
    if self.isEmpty() == True:
      return
    else:
      return self.front.data
      
  def traverse(self):
    
    if self.isEmpty() == True:
      return "Queue is Empty!"
    else:
      temp = self.front
      while temp:
        print(temp.data, end = " ")
        temp = temp.next

if __name__ == "__main__":
  
  pq = PriorityQueue()
  pq.push(14, 1)
  pq.push(18, 2)
  pq.push(16, 3)
  pq.push(12, 0)
  
  pq.traverse()
  
  pq.pop()


     import java.util.* ;

class Main
{
    
static class Node {
    int data;
    
    int priority;
    
    Node next;
    
}

static Node node = new Node();
    
static Node newNode(int d, int p)
{
    Node temp = new Node();
    temp.data = d;
    temp.priority = p;
    temp.next = null;
    
    return temp;
}
    
static int peek(Node head)
{
    return (head).data;
}
    
static Node pop(Node head)
{
    Node temp = head;
    (head) = (head).next;
    return head;
}
    
static Node 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;
    }
    return head;
}
    
static int isEmpty(Node head)
{
    return ((head) == null)?1:0;
}
    
public static void main(String args[])
{
    // Create a Priority Queue
    // 70.40.50.60
    Node pq = newNode(14, 1);
    pq =push(pq, 18, 2);
    pq =push(pq, 16, 3);
    pq =push(pq, 12, 0);
    
    while (isEmpty(pq)==0) {
        System.out.printf("%d ", peek(pq));
        pq=pop(pq);
    }
    
}
}


#include 
using namespace std;

// Node
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);

    // Create new Node
    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
    // 70->40->50->60
    Node* pq = newNode(14, 1);
    push(&pq, 18, 2);
    push(&pq, 16, 3);
    push(&pq, 12, 0);

    while (!isEmpty(&pq))
    {
        cout << " " << peek(&pq);
        pop(&pq);
    }
    return 0;
}

The above code for the linked list implementation of the priority queue is implemented in the Python Editor, C++ Playground, and Java Playground.

Output

12 14 18 16

Read More: Linked Lists in Data Structures

3. Implement Priority Queue Using Heaps


 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 Heap {
  // Function to heapify the tree
  void heapify(ArrayList hT, int i) {
    int size = hT.size();
    // Find the largest among root, left child and right child
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && hT.get(l) > hT.get(largest))
      largest = l;
    if (r < size && hT.get(r) > hT.get(largest))
      largest = r;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      int temp = hT.get(largest);
      hT.set(largest, hT.get(i));
      hT.set(i, temp);

      heapify(hT, largest);
    }
  }

  // Function to insert an element into the tree
  void insert(ArrayList hT, int newNum) {
    int size = hT.size();
    if (size == 0) {
      hT.add(newNum);
    } else {
      hT.add(newNum);
      for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(hT, i);
      }
    }
  }

  // Function to delete an element from the tree
  void deleteNode(ArrayList hT, int num) {
    int size = hT.size();
    int i;
    for (i = 0; i < size; i++) {
      if (num == hT.get(i))
        break;
    }

    int temp = hT.get(i);
    hT.set(i, hT.get(size - 1));
    hT.set(size - 1, temp);

    hT.remove(size - 1);
    for (int j = size / 2 - 1; j >= 0; j--) {
      heapify(hT, j);
    }
  }

  // Print the tree
  void printArray(ArrayList array, int size) {
    for (Integer i : array) {
      System.out.print(i + " ");
    }
    System.out.println();
  }

  // Driver code
  public static void main(String args[]) {

    ArrayList array = new ArrayList();
    int size = array.size();

    Heap h = new Heap();
    h.insert(array, 3);
    h.insert(array, 4);
    h.insert(array, 9);
    h.insert(array, 5);
    h.insert(array, 2);

    System.out.print("Max-Heap array: ");
    h.printArray(array, size);

    h.deleteNode(array, 4);
    System.out.print("After deleting an element: ");
    h.printArray(array, size);
  }
}


#include 
#include 
using namespace std;

// Function to swap position of two elements
void swap(int *a, int *b) {
  int temp = *b;
  *b = *a;
  *a = temp;
}

// Function to heapify the tree
void heapify(vector &hT, int i) {
  int size = hT.size();
  
  // Find the largest among root, left child and right child
  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;

  // Swap and continue heapifying if root is not largest
  if (largest != i) {
    swap(&hT[i], &hT[largest]);
    heapify(hT, largest);
  }
}

// Function to insert an element into the tree
void insert(vector &hT, int newNum) {
  int size = hT.size();
  if (size == 0) {
    hT.push_back(newNum);
  } else {
    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 &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);
  }
}

// Print the tree
void printArray(vector &hT) {
  for (int i = 0; i < hT.size(); ++i)
    cout << hT[i] << " ";
  cout << "\n";
}

// Driver code
int main() {
  vector 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);
}

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.


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;
    TreeNode right;

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

public class PriorityQueueBST {
    private TreeNode root;

    public PriorityQueueBST() {
        this.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() {
        TreeNode maxNode = findMax(root);
        root = deleteHelper(root, maxNode.val);
        return maxNode.val;
    }

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

    private TreeNode deleteHelper(TreeNode node, int val) {
        if (node == null) {
            return null;
        }
        if (val < node.val) {
            node.left = deleteHelper(node.left, val);
        } else if (val > node.val) {
            node.right = deleteHelper(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 = deleteHelper(node.left, temp.val);
        }
        return node;
    }

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

    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());
        }
    }
}


 #include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

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

class PriorityQueueBST {
private:
    TreeNode *root;

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

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

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

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

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

    int deleteMax() {
        TreeNode* maxNode = findMax(root);
        root = deleteHelper(root, maxNode->val);
        return maxNode->val;
    }

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

int main() {
    PriorityQueueBST pq;
    pq.insert(10);
    pq.insert(20);
    pq.insert(5);
    pq.insert(15);

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

    return 0;
}

Output

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 largest/smallest element

Advantages of Priority Queue

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.

Disadvantages of Priority Queue

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.

Q4. What are the applications of the 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

01 Career Opportunities

02 Beginner

03 Intermediate

04 Advanced

05 Questions

06 Training Programs

Priority Queue in Data Structures

Data Structures & Algorithms Free Course

Data Structures Priority Queue: An Overview

What is a Priority Queue in Data Structures?

Priority Queue in Data Structure Example

Characteristics of a Priority Queue in Data Structures

Representation of a Priority Queue in Data Structures

Types of Priority Queue in Data Structures

Operations on Priority Queue

1. Insertion: enqueue()

2. Deletion: dequeue()

3. Peek

Syntax to perform peek operation on both, max and min heap

4. Extract-Max/Min from the Priority Queue

Implementation of Priority Queue

1. Implement Priority Queue Using Array

Output

2) Implement Priority Queue Using Linked List

Output

3. Implement Priority Queue Using Heaps

Output

4. Implement Priority Queue Using Binary Search Tree

Output

Applications of Priority Queue

Advantages of Priority Queue

Disadvantages of Priority Queue

Summary

FAQs

Q1. What is priority queue in data structure?

Q2. What is priority queue order?

Q3. What is a priority queue of lists?

Q4. What are the applications of the priority queue?

About Author