There are two kinds of priority queues: the maximum priority queue, the current largest element priority queue; Minimum priority queue, the current smallest element is queued first.

PriorityQueue is implemented by using a small top heap represented by an array, as shown in the figure below

First of all, any node is smaller than its left and right children, and in addition, for any node, let’s say it has a subscript of n:

  • Left child: 2 * n + 1
  • The right child is 2 times n plus 2
  • The parent :(n + 1) / 2

1 structure

  1. Member variables

  2. The constructor

    It looks like there are seven but there are only four

    All but the first are initialized on PriorityQueue, SortedSet, and other collections, where the SortedSet is already sorted and does not require any special processing, and the others require a call to heapify() to handle them.

    Go into the heapify() source code and you’ll see that the siftDown() function is used, which we’ll cover later

2 increase

The semantics of add and offer are the same. Add also calls offer. The main functions of add are grow and siftUp. After the expansion function, let’s examine the filter function (siftUp/siftDown).

Assuming that the element to be inserted is 4, the GIF has a flaw that after the comparison, instead of swapping 4 with the node to be compared, the parent is simply moved down.

3 remove

SiftDown is similar to SiftUp, both of which contain two methods: with or without a comparator. Here, we can take an analysis.

4 the query

Because the query does not involve structural changes or adjustments, the source code is very simple.

5 capacity

Size enlargement occurs when adding elements, and occurs when size >= queue.length.