How to Implement Priority Queue?
Priority queue can be implemented using the following data structures:
- Arrays
- Linked list
- Heap data structure
- Binary search tree
Let’s discuss all these in detail.
1) Implement Priority Queue Using Array:
A simple implementation is to use an array of the following structure.
struct item {
int item;
int priority;
}
- enqueue(): This function is used to insert new data into the queue.
- dequeue(): This function removes the element with the highest priority from the queue.
- peek()/top(): This function is used to get the highest priority element in the queue without removing it from the queue.
Arrays |
enqueue() |
dequeue() |
peek() |
---|---|---|---|
Time Complexity |
O(1) |
O(n) |
O(n) |
C++
// C++ program to implement Priority Queue // using Arrays #include <bits/stdc++.h> 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 // into priority queue 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(10, 2); enqueue(14, 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; } |
Java
// Java program to implement Priority Queue // using Arrays import java.util.*; // Structure for the elements in the // priority queue class item { public int value; public int priority; }; class GFG { // 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( 10 , 2 ); enqueue( 14 , 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); } } // this code is contributed by phasing17 |
Python3
import sys # Structure for the elements in the # priority queue class item : value = 0 priority = 0 class GFG : # 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 GFG.size + = 1 # Insert the element GFG.pr[GFG.size] = item() GFG.pr[GFG.size].value = value GFG.pr[GFG.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 < = GFG.size) : # If priority is same choose # the element with the # highest value if (highestPriority = = GFG.pr[i].priority and ind > - 1 and GFG.pr[ind].value < GFG.pr[i].value) : highestPriority = GFG.pr[i].priority ind = i elif (highestPriority < GFG.pr[i].priority) : highestPriority = GFG.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 = GFG.peek() # Shift the element one index before # from the position of the element # with highest priority is found i = ind while (i < GFG.size) : GFG.pr[i] = GFG.pr[i + 1 ] i + = 1 # Decrease the size of the # priority queue by one GFG.size - = 1 @staticmethod def main( args) : # Function Call to insert elements # as per the priority GFG.enqueue( 10 , 2 ) GFG.enqueue( 14 , 4 ) GFG.enqueue( 16 , 4 ) GFG.enqueue( 12 , 3 ) # Stores the top element # at the moment ind = GFG.peek() print (GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print (GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print (GFG.pr[ind].value) if __name__ = = "__main__" : GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# program to implement Priority Queue // using Arrays using System; // Structure for the elements in the // priority queue public class item { public int value; public int priority; }; public class GFG { // 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 = int .MinValue; 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(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); } } //this code is contributed by phasing17 |
Javascript
// JavaScript program to implement Priority Queue // using Arrays // Structure for the elements in the // priority queue class item { constructor() { this .value; this .priority; } }; // Store the element of a priority queue let pr = []; for ( var i = 0; i < 100000; i++) pr.push( new item()); // Pointer to the last index let size = -1; // Function to insert a new element // into priority queue function enqueue(value, 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 function peek() { let highestPriority = Number.MIN_SAFE_INTEGER; let ind = -1; // Check for the element with // highest priority for ( var 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 function dequeue() { // Find the position of the element // with highest priority let ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for ( var i = ind; i < size; i++) { pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment let ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // this code is contributed by phasing17 |
16 14 12
Note: Read this article for more details.
2) Implement Priority Queue Using Linked List:
In a LinkedList 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, which is formed using linked lists. The functions like push(), pop(), and peek() are used to implement a priority queue using a linked list and are explained as follows:
- push(): This function is used to insert new data into the queue.
- pop(): This function removes the element with the highest priority from the queue.
- peek() / top(): This function is used to get the highest priority element in the queue without removing it from the queue.
Linked List |
push() |
pop() |
peek() |
---|---|---|---|
Time Complexity |
O(n) |
O(1) |
O(1) |
C++
// C++ code to implement Priority Queue // using Linked List #include <bits/stdc++.h> using namespace std; // Node typedef struct node { int data; // Lower values indicate // higher priority int priority; struct node* next; } Node; // Function to create a new node Node* newNode( int d, int p) { Node* temp = (Node*) malloc ( sizeof (Node)); temp->data = d; temp->priority = p; temp->next = NULL; return temp; } // Return the value at head int peek(Node** head) { return (*head)->data; } // Removes the element with the // highest priority form the list void pop(Node** head) { Node* temp = *head; (*head) = (*head)->next; free (temp); } // Function to push according to priority void push(Node** head, int d, int p) { Node* start = (*head); // Create new Node Node* temp = newNode(d, p); // Special Case: The head of list has // lesser priority than new node if ((*head)->priority < p) { // Insert New Node before head temp->next = *head; (*head) = temp; } else { // Traverse the list and find a // position to insert new node while (start->next != NULL && start->next->priority > p) { start = start->next; } // Either at the ends of the list // or at required position temp->next = start->next; start->next = temp; } } // Function to check is list is empty int isEmpty(Node** head) { return (*head) == NULL; } // Driver code int main() { // Create a Priority Queue // 7->4->5->6 Node* pq = newNode(4, 1); push(&pq, 5, 2); push(&pq, 6, 3); push(&pq, 7, 0); while (!isEmpty(&pq)) { cout << " " << peek(&pq); pop(&pq); } return 0; } |
Java
// Java code to implement Priority Queue // using Linked List import java.util.* ; class Solution { // Node static class Node { int data; // Lower values indicate higher priority int priority; Node next; } static Node node = new Node(); // Function to Create A New Node static Node newNode( int d, int p) { Node temp = new Node(); temp.data = d; temp.priority = p; temp.next = null ; return temp; } // Return the value at head static int peek(Node head) { return (head).data; } // Removes the element with the // highest priority from the list static Node pop(Node head) { Node temp = head; (head) = (head).next; return head; } // Function to push according to priority static Node push(Node head, int d, int p) { Node start = (head); // Create new Node Node temp = newNode(d, p); // Special Case: The head of list has lesser // priority than new node. So insert new // node before head node and change head node. if ((head).priority < p) { // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority > p) { start = start.next; } // Either at the ends of the list // or at required position temp.next = start.next; start.next = temp; } return head; } // Function to check is list is empty static int isEmpty(Node head) { return ((head) == null )? 1 : 0 ; } // Driver code public static void main(String args[]) { // Create a Priority Queue // 7.4.5.6 Node pq = newNode( 4 , 1 ); pq =push(pq, 5 , 2 ); pq =push(pq, 6 , 3 ); pq =push(pq, 7 , 0 ); while (isEmpty(pq)== 0 ) { System.out.printf( "%d " , peek(pq)); pq=pop(pq); } } } // This code is contributed by ishankhandelwals. |
Python
# Python3 code to implement Priority Queue # using Singly Linked List # Class to create new node which includes # Node Data, and Node Priority class PriorityQueueNode: def _init_( self , value, pr): self .data = value self .priority = pr self . next = None # Implementation of Priority Queue class PriorityQueue: def _init_( self ): self .front = None # Method to check Priority Queue is Empty # or not if Empty then it will return True # Otherwise False def isEmpty( self ): return True if self .front = = None else False # Method to add items in Priority Queue # According to their priority value def push( self , value, priority): # Condition check for checking Priority # Queue is empty or not if self .isEmpty() = = True : # Creating a new node and assigning # it to class variable self .front = PriorityQueueNode(value, priority) # Returning 1 for successful execution return 1 else : # Special condition check to see that # first node priority value if self .front.priority < priority: # Creating a new node newNode = PriorityQueueNode(value, priority) # Updating the new node next value newNode. next = self .front # Assigning it to self.front self .front = newNode # Returning 1 for successful execution return 1 else : # Traversing through Queue until it # finds the next smaller priority node temp = self .front while temp. next : # If same priority node found then current # node will come after previous node if priority > = temp. next .priority: break temp = temp. next newNode = PriorityQueueNode(value, priority) newNode. next = temp. next temp. next = newNode # Returning 1 for successful execution return 1 # Method to remove high priority item # from the Priority Queue def pop( self ): # Condition check for checking # Priority Queue is empty or not if self .isEmpty() = = True : return else : # Removing high priority node from # Priority Queue, and updating front # with next node self .front = self .front. next return 1 # Method to return high priority node # value Not removing it def peek( self ): # Condition check for checking Priority # Queue is empty or not if self .isEmpty() = = True : return else : return self .front.data # Method to Traverse through Priority # Queue def traverse( self ): # Condition check for checking Priority # Queue is empty or not if self .isEmpty() = = True : return "Queue is Empty!" else : temp = self .front while temp: print (temp.data, end = " " ) temp = temp. next # Driver code if _name_ = = "_main_" : # Creating an instance of Priority # Queue, and adding values # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push( 4 , 1 ) pq.push( 5 , 2 ) pq.push( 6 , 3 ) pq.push( 7 , 0 ) # Traversing through Priority Queue pq.traverse() # Removing highest Priority item # for priority queue pq.pop() |
C#
// C# code to implement Priority Queue // using Linked List using System; class GFG { // Node public class Node { public int data; // Lower values indicate // higher priority public int priority; public Node next; } public static Node node = new Node(); // Function to Create A New Node public static Node newNode( int d, int p) { Node temp = new Node(); temp.data = d; temp.priority = p; temp.next = null ; return temp; } // Return the value at head public static int peek(Node head) { return (head).data; } // Removes the element with the // highest priority from the list public static Node pop(Node head) { Node temp = head; (head) = (head).next; return head; } // Function to push according to priority public static Node push(Node head, int d, int p) { Node start = (head); // Create new Node Node temp = newNode(d, p); // Special Case: The head of list // has lesser priority than new node. // So insert new node before head node // and change head node. if ((head).priority < p) { // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority > p) { start = start.next; } // Either at the ends of the list // or at required position temp.next = start.next; start.next = temp; } return head; } // Function to check is list is empty public static int isEmpty(Node head) { return ((head) == null ) ? 1 : 0; } // Driver code public static void Main( string [] args) { // Create a Priority Queue // 7.4.5.6 Node pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write( "{0:D} " , peek(pq)); pq = pop(pq); } } } // This code is contributed by ishankhandelwals. |
Javascript
// JavaScript code to implement Priority Queue // using Linked List // Node class Node { // Lower values indicate // higher priority constructor() { this .data = 0; this .priority = 0; this .next = null ; } } var node = new Node(); // Function to Create A New Node function newNode(d, p) { var temp = new Node(); temp.data = d; temp.priority = p; temp.next = null ; return temp; } // Return the value at head function peek(head) { return head.data; } // Removes the element with the // highest priority from the list function pop(head) { var temp = head; head = head.next; return head; } // Function to push according to priority function push(head, d, p) { var start = head; // Create new Node var temp = newNode(d, p); // Special Case: The head of list // has lesser priority than new node. // So insert new node before head node // and change head node. if (head.priority < p) { // Insert New Node before head temp.next = head; head = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority > p) { start = start.next; } // Either at the ends of the list // or at required position temp.next = start.next; start.next = temp; } return head; } // Function to check is list is empty function isEmpty(head) { return head == null ? 1 : 0; } // Driver code // Create a Priority Queue // 7.4.5.6 var pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq), " " ); pq = pop(pq); } // This code is contributed by ishankhandelwals. |
6 5 4 7
Refer to this article for more details.
Note: We can also use Linked List, time complexity of all operations with linked list remains same as array. The advantage with linked list is deleteHighestPriority() can be more efficient as we don’t have to move items.
3) Implement Priority Queue Using Heaps:
Binary Heap is generally preferred for priority queue implementation because heaps provide better performance compared to arrays or LinkedList. Considering the properties of a heap, The entry with the largest key is on the top and can be removed immediately. It will, however, take time O(log n) to restore the heap property for the remaining keys. However if another entry is to be inserted immediately, then some of this time may be combined with the O(log n) time needed to insert the new entry. Thus the representation of a priority queue as a heap proves advantageous for large n, since it is represented efficiently in contiguous storage and is guaranteed to require only logarithmic time for both insertions and deletions. Operations on Binary Heap are as follows:
- insert(p): Inserts a new element with priority p.
- extractMax(): Extracts an element with maximum priority.
- remove(i): Removes an element pointed by an iterator i.
- getMax(): Returns an element with maximum priority.
- changePriority(i, p): Changes the priority of an element pointed by i to p.
Binary Heap |
insert() |
remove() |
peek() |
---|---|---|---|
Time Complexity |
O(log n) |
O(log n) |
O(1) |
Refer to this article for code implementation.
4) Implement Priority Queue Using Binary Search Tree:
A Self-Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc. can also be used to implement a priority queue. Operations like peek(), insert() and delete() can be performed using BST.
Binary Search Tree | peek() | insert() | delete() |
---|---|---|---|
Time Complexity | O(1) | O(log n) | O(log n) |
What is Priority Queue | Introduction to Priority Queue
A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values.
In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its priority value. For example, if you add an element with a high priority value to a priority queue, it may be inserted near the front of the queue, while an element with a low priority value may be inserted near the back.
There are several ways to implement a priority queue, including using an array, linked list, heap, or binary search tree. Each method has its own advantages and disadvantages, and the best choice will depend on the specific needs of your application.
Priority queues are often used in real-time systems, where the order in which elements are processed can have significant consequences. They are also used in algorithms to improve their efficiencies, such as Dijkstra’s algorithm for finding the shortest path in a graph and the A* search algorithm for pathfinding.
Contact Us