Priority Queue Insertion and Deletion in Java
Priority Queue Insertion and Deletion
Priority Queue Insertion and Deletion in Java explains how elements are added and removed in a priority queue based on their priority rather than insertion order. Unlike a normal queue that follows FIFO (First In, First Out), a priority queue processes elements according to priority levels.
Priority Queue Insertion And Deletion
Introduction to Priority Queue
A priority is basically an extension of the general queue. A major difference is that dequeuing happens based on the priority of each item in the queue.
We have two types of priority queue:
- Max Priority Queue – A larger priority value means higher priority
- Min Priority Queue – A smaller priority value means lower priority
By default, if nothing is mentioned it means that the Priority queue is a min priority queue.
A Priority Queue can be implemented using:
- Arrays
- Linked List
- Heaps
You can check these pages here for implementation using Linked List and arrays
We will be discussing the array approach here.
Operations:
- enqueue(): To insert a new item at the end of the queue.
- dequeue(): To remove the element with the highest priority from the queue.
- peek()/top(): To get the highest priority element in the queue without dequeuing the item.
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Algorithm for Priority Queue Insertion And Deletion
Algorithm: Insertion
1. Insert element at the end of heap
2. Compare element with parent
3. If smaller than parent
Swap elements
4. Repeat until heap property is satisfied
Algorithm: Deletion
1. Remove the root element (highest priority)
2. Move the last element to root
3. Compare root with children
4. Swap with smallest child
5. Repeat until heap property is restored
Java Code for Priority Queue Insertion And Deletion
// Java program for insertion and deletion in priority queue
// using queue class
import java.util.*;
class Main{
// Main Method
public static void main(String[] args)
{
// Creating a priority queue
PriorityQueue pq = new PriorityQueue<>();
pq.add("Insta");
pq.add("Prep");
pq.add("Prime");
System.out.println("Priority Queue is : " + pq);
System.out.println("Element accessed is : " + pq.remove());
System.out.println("Element accessed is : " + pq.remove());
}
}
Output : Priority Queue is : [Insta, Prep, Prime] Element accessed is : Insta Element accessed is : Prep
Space Complexity: O(n)
Before performing operations:
- Check if queue is empty before deletion
- Avoid inserting null elements
- Ensure elements are comparable
Example:
if (pq.isEmpty()) {
System.out.println("Queue is empty");
}
Frequently Asked Questions
Answer:
Insertion means adding an element to the priority queue using offer() or add().
Answer:
Deletion removes the element with the highest priority using poll() or remove().
Answer:
Insertion takes O(log n) time.
Answer:
poll() returns null if the queue is empty, while remove() throws an exception.
Answer:
Java PriorityQueue is a min heap by default.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
