/ Java  

Java PriorityQueue

PriorityQueue

The PriorityQueue class was introduced in Java 1.5.

PriorityQueue is an unbounded queue based on the priority heap. Elements in the priority queue can be sorted naturally by default or provided Comparator when the queue is instantiated. When Comparator is not specified, it is default to a minimum heap.

PriorityQueue does not allow null values and does not support non-comparable objects, such as user-defined classes. Priority queues require Java Comparable and Comparator interfaces to sort objects, and the elements in them are processed according to priority when sorting.

The size of the PriorityQueue is unlimited, but you can specify an initial size when you create it. When we add elements to the priority queue, the queue size will automatically increase.

PriorityQueue is not thread-safe, so Java provides PriorityBlockingQueue (implements the BlockingQueue interface) for Java multi-threaded environments.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<Integer>();
        priorityQueue.add(2);
        priorityQueue.add(1);
        priorityQueue.add(3);

        while (!priorityQueue.isEmpty()) {
            Integer i = priorityQueue.poll();
            System.out.println(i);
        }

        Comparator<Item> comparator = new Comparator<Item>() {
            @Override
            public int compare(Item o1, StuItemdent o2) {
                return (o1.price - o2.price);
            }
        };

        Queue<Item> priorityQueue2 = new PriorityQueue<Item>(comparator);
        priorityQueue2.add(new Item("B", 2));
        priorityQueue2.add(new Item("A", 1));
        priorityQueue2.add(new Item("C", 3));

        while (!priorityQueue2.isEmpty()) {
            Item s = priorityQueue2.poll();
            System.out.println(s.toString());
        }
    }

    public static class Item {
        private String name;
        private double price

        public Item(String name, double price) {
            this.name = name;
            this.price = price;
        }

        public String toString() {
            return name + "-" + price;
        }
    }
}

Output:

1
2
3
4
5
6
1
2
3
A-1
B-2
C-3

How PriorityQueue is implemented

Implemented through the heap, specifically a small top heap implemented through a complete binary tree (the weight of any non-leaf node is not greater than the weight of its left and right child nodes), which means that array can be used as the underlying implementation of PriorityQueue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

/**
 * The number of elements in the priority queue.
 */
int size;

The relationship between the index of parent and child nodes is as follows:

  • leftNo = parentNo * 2 + 1
  • rightNo = parentNo * 2 + 2
  • parentNo = (nodeNo-1) / 2

The time complexity of the add(E e) and offer(E e) operations is log(N):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean add(E e) {
    return offer(e);
}
    
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
        
    modCount++;
    int i = size;

    if (i >= queue.length)
        grow(i + 1);

    siftUp(i, e);
    size = i + 1;

    return true;
}

The time complexity of the poll() operation is log (N):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}