Priority Queue is an extension of queue with the following properties:
- Every item has a priority associated with it.
- An element with high priority is dequeued before an element with low priority.
- If two elements have the same priority, they are served according to their order in the queue.
In this example, element with maximum ASCII value will have the highest priority.
- CPU Scheduling
- Graph algorithms
- Dijkstra's Shortest Path
- Prim's Minimum Spanning Tree
- etc...
- All queue applications where priority is involved.
- insert(item, priority)
- getHighestPriority()
- deleteHighestPriority()
- Array Implementation
- Heap Implementation
- Simple implementation
insert
can be implemented by adding an item at end of array inO(1)
time.
- Better performanced compared to arrays or linked list.
- With a Binary Heap,
getHighestPriority()
can be implemented inO(1)
time,insert
inO(log n)
time anddeleteHighestPriority()
can also be implemented inO(log n)
time (most common implementation). - With a Fibonaci Heap,
insert
andgetHighestPriority
can be implemented inO(1)
amortized time anddeleteHighestPriority
inO(log n)
amortized time.
java.util
provides PriorityQueue<E>
class that implements Serializable
, Iterable<E>
, Collection<E>
, Queue<E>
interfaces.
Some important points:
- It provides
O(log n)
time foradd
andpoll
methods. - Doesn't permit
null
. - Can't create PriorityQueue ob Objects that are non-comparable.
- Unbound queues.
- If multiple elements are tied for least value, ties are broken arbitrarily.
- Is not thread-safe (Java provides
PriorityBlockingQueue
class that implements theBlockingQueue
interface).
See more examples in my [Datastructures in Java repository]((https://github.com/herrera-ignacio/datastructures-in-java/tree/master/src/main/java/linear/queue)