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

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

First, any node is smaller than its left and right children. In addition, for any node, suppose its subscript is n:

  • Left child: 2 * n + 1
  • Right child: 2 * n + 2
  • The parent is (n + 1) / 2

1 structure

  1. Member variables

  2. The constructor

    It looks like there are seven but there are only four

    In addition to the first, the others initialize PriorityQueue, SortedSet, and other collections, where SortedSet is already sorted so no special processing is required, while the others require a call to Heapify ().

    If you go into the heapify() source code, you can see the use of the siftDown() function, which will be covered later

2 increase

The semantics of add and offer are the same. Add also calls offer, mainly grow and siftUp. Next to the expansion function, we will analyze the filter function (siftUp/siftDown).

Let’s say the element to be inserted is 4. One of the drawbacks of this GIF is that instead of swapping the 4 with the node to be compared, the parent node is simply removed.

3 remove

SiftDown and siftUp are similar in that both methods contain a comparator and no comparator.

4 the query

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

5 capacity

Capacity expansion occurs when an element is added, and occurs when size >= queue.length.