Implement Priority Queue using Linked Lists.
- push(): This function is used to insert a 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.
Priority Queues can be implemented using common data structures like arrays, linked-lists, heaps and binary trees.
Prerequisites :
Linked Lists, Priority Queues
The list is so created so that the highest priority element is always at the head of the list. The list is arranged in descending order of elements based on their priority. This allow us to remove the highest priority element in O(1) time. To insert an element we must traverse the list and find the proper position to insert the node so that the overall order of the priority queue is maintained. This makes the push() operation takes O(N) time. The pop() and peek() operations are performed in constant time.
Algorithm :
PUSH(HEAD, DATA, PRIORITY):
- Step 1: Create new node with DATA and PRIORITY
- Step 2: Check if HEAD has lower priority. If true follow Steps 3-4 and end. Else goto Step 5.
- Step 3: NEW -> NEXT = HEAD
- Step 4: HEAD = NEW
- Step 5: Set TEMP to head of the list
- Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY
- Step 7: TEMP = TEMP -> NEXT
[END OF LOOP]- Step 8: NEW -> NEXT = TEMP -> NEXT
- Step 9: TEMP -> NEXT = NEW
- Step 10: End
POP(HEAD):
- Step 1: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT.
- Step 2: Free the node at the head of the list
- Step 3: End
PEEK(HEAD):
- Step 1: Return HEAD -> DATA
- Step 2: End
Below is the implementation of the algorithm :
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 from 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. So // insert newnode 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; } } // 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; } // This code is contributed by shivanisinghss2110 |
C
// C code to implement Priority Queue // using Linked List #include <stdio.h> #include <stdlib.h> // 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 from 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. 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; } } // 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)) { printf("%d ", 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 Arnab Kundu |
Python3
# 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() # This code is contributed by himanshu kanojiya |
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 Shrikant13 |
Javascript
<script> // 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) { document.write(peek(pq) + " "); pq = pop(pq); } // This code is contributed by rdtank. </script> |
Output:
7 4 5 6
Time Complexities and Comparison with Binary Heap:
peek() push() pop()
-----------------------------------------
Linked List | O(1) O(n) O(1)
|
Binary Heap | O(1) O(Log n) O(Log n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
