Java PriorityQueue Example

Tags: , ,

Queue is an important data structure that offers first-in, first-out service. However, some items or tasks put in the queue may be more important than others (higher priority), and we want the items with highest priority to be served first.  We need a data structure to put the item or task with highest oder at the head of the queue. Such a data structure is called PriorityQueue.  Heaps are usually used as the underlying data structures of priority queues. 

There are basically two operations for a priority queue: remove the maximum (or minimum) and insert new items to the queue.  When we implement a priority queue using max Heap, the root of the heap is the maximum value. After we remove the root, we get the largest value from the heap, then the heap will be reorganized such that the second largest item will be the new root. 

Java PriorityQueue

The java.util.PriorityQueue class is an unbounded priority queue based on a priority heap. Here are some properties of Java PriorityQueue:

  • The items stored in a java priority queue are ordered using their natural ordering, or by a Comparator offered at queue construction time, depending on which constructor is used.  See this post on how to use Comparable or Comparator in Java

    So in default, Java PriorityQueue is a min heap, which means the head of the queue is the minimum value. To make java PriorityQueue a max heap, which means the head of the queue is the item with maximum value, we must use customized comparator. 

  • A java priority queue does not allow null items.

  • A java priority queue  does not allow insertion of non-comparable objects if no comparator is used.

The methods of Java PriorityQueue

Constructors:

PriorityQueue()
creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

PriorityQueue(Collection<? extends E> c)
Build a PriorityQueue containing the elements in the specified collection.

PriorityQueue(int initialCapacity)
Build a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

PriorityQueue(PriorityQueue<? extends E> c)
creates a PriorityQueue containing the elements in the specified priority queue.

PriorityQueue(SortedSet<? extends E> c)
creates a PriorityQueue containing the elements in the specified sorted set.

Methods

add(E e)
The add method inserts the specified element into this priority queue.

clear()
After call the clear method, all of the elements from this priority queue will be removed.

comparator()
Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.

contains(Object o)
Returns true if this queue contains the specified element.

iterator()
Returns an iterator over the elements in this queue.

offer(E e)
Inserts the specified element into this priority queue.

peek()
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.

remove(Object o)
Removes a single instance of the specified element from this queue, if it is present.

size()
Returns the number of elements in this collection.

toArray()
Returns an array containing all of the elements in this queue.

toArray(T[] a)
Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.

Examples of java Priority queue:

We first store integers into the java priority queue to show that it is actually a min heap. To make java priority queue a max heap, we should define our own comparator by Overriding the compare method of the Comparator interface. 

We also define a Task class with a priority attribute. The example shows that once we put the tasks into the priority queue, the heap of the queue will be the tasks with the highest priority score. 

The following is the output of the program:

This is to show java priorityqueue is a min heap in default
0
1
2
3
4

Use custom Comparator to make java priorityqueue a max heap…
4
3
2
1
0

Another example to show The default Java Priority Query is a min heap…
Task < priority=0.0 name = task-0>
Task < priority=1.0 name = task-1>
Task < priority=2.0 name = task-2>
Task < priority=3.0 name = task-3>
Task < priority=4.0 name = task-4>

Another example to use custom comparator to make java priority queue a max heap…
Task < priority=4.0 name = task-4>
Task < priority=3.0 name = task-3>
Task < priority=2.0 name = task-2>
Task < priority=1.0 name = task-1>
Task < priority=0.0 name = task-0>

Some applications of Java PriorityQueue

Find  the kth largest element in an unsorted array

Meeting rooms II

Reference:

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf