Priority Queue

 A Priority Queue in Java is a specific type of queue implementation where elements are dequeued (removed) based on their priority, rather than the standard First-In, First-Out (FIFO) order.

🥇 Priority Queue Summary

• Structure: It is based on the heap data structure, specifically a Min-Heap by default, where the smallest element is at the root. You can customize it to be a Max-Heap using a Comparator.

• Ordering: Elements are ordered according to their natural ordering (if they implement Comparable) or by a Comparator provided at the time of construction.

• Priority:

  • In a Min-Heap (default), the element with the lowest value is considered the highest priority and is retrieved first.

  • In a Max-Heap, the element with the highest value is considered the highest priority.

• Implementation: In the Java Collections Framework, it is implemented by the java.util.PriorityQueue class, which is part of the Collection and Queue interfaces.

• Time Complexity:

  • Insertion (add/offer): O(log n)

  • Removal (remove/poll): O(log n)

  • Inspection (peek): O(1)

• Capacity: It is an unbounded queue, but it has an internal capacity that automatically increases as elements are added.

• Thread Safety: It is not synchronized (not thread-safe). If you need thread-safe priority queue, use java.util.concurrent.PriorityBlockingQueue.

⚙️ Key Methods

The PriorityQueue implements the Queue interface, so it uses the standard queue methods, but their behavior reflects the priority-based ordering.

Method	Purpose	Returns	Time Complexity	Notes
add(E e)	Inserts the specified element into the priority queue.	boolean (always true in PriorityQueue)	O(log n)	Throws IllegalStateException if no space is available (not usually an issue as it's unbounded).
offer(E e)	Inserts the specified element.	boolean (always true in PriorityQueue)	O(log n)	Preferred over add() for capacity-constrained queues (though PriorityQueue is unbounded).
peek()	Retrieves, but does not remove, the head (highest priority element) of this queue.	E (element) or null	O(1)	Returns null if the queue is empty.
element()	Retrieves, but does not remove, the head of this queue.	E (element)	O(1)	Throws NoSuchElementException if the queue is empty.
poll()	Retrieves and removes the head (highest priority element) of this queue.	E (element) or null	O(log n)	Returns null if the queue is empty. Preferred over remove().
remove()	Retrieves and removes the head of this queue.	E (element)	O(log n)	Throws NoSuchElementException if the queue is empty.
remove(Object o)	Removes a single instance of the specified element, if it is present.	boolean	O(n)	Not efficient as it searches linearly.
size()	Returns the number of elements in the queue.	int	O(1)

 PriorityQueue<Patient> hospitalQueue = new PriorityQueue<>( (p1, p2) -> Integer.compare(p2.severity, p1.severity) );