an introduction to

The PriorityQueue class is in Java 1 5 and as part of the Java Collections Framework. PriorityQueue is an unbounded queue based on the priority heap. The elements in the priority queue can be sorted naturally by default or when the queue is instantiated through the provided comparator.

The priority queue does not allow null values, Moreover, non comparable objects, such as user-defined classes, are not supported. Priority queues require the use of Java comparable and comparator interfaces to sort objects, and the elements in them will be processed according to priority. If you insert a non comparable object, a ClassCastException exception will be thrown.

The head of the priority queue is the smallest element based on natural sorting or comparator sorting. If multiple objects have the same sort, it is possible to take any one of them at random. When we get the queue, we return the header object of the queue.

The size of the priority queue is unlimited, but the initial size can be specified at the time of creation. Its internal "capacity" manages the size of the array, which is used to store the elements of the queue. It is always at least as large as the queue size. When we add elements to the priority queue, the queue size will increase automatically. Details of the growth strategy were not specified.

This class and its iterators implement all optional methods of the collection and iterator interfaces. The iterator () method provided by the iterator does not guarantee that the elements of the priority queue are traversed according to any special order. If you need an orderly traversal, consider using arrays sort(pq.toArray()).

PriorityQueue is non thread safe, so Java provides priorityblockingqueue (implementing the BlockingQueue interface) for Java multithreading environment.

Implementation note: this implementation provides o (log (n)) time complexity. For queue in and queue out methods: offer, poll, remove() and add; Linear time o (n) for remove (object) and contains (object) methods; And constant time o (1) for retrieval methods: PEEK, element and size.

data structure

Binary heap is a special kind of heap. Binary heap is a complete binary tree or an approximately complete binary tree. There are two types of binary heap: maximum heap and minimum heap. Maximum heap: the key value of the parent node is always greater than or equal to the key value of any child node; Minimum heap: the key value of the parent node is always less than or equal to the key value of any child node.

Priority queue is a balanced binary heap (balanced binary tree). All child nodes in the tree must be greater than or equal to the parent node without maintaining the size relationship. It is a minimum heap.

Size relationship between nodes:

-Leaf and non leaf nodes:

Source code analysis of PriorityQueue

Basic properties

Let's first look at the definition of PriorityQueue

You can see that PriorityQueue inherits the abstractqueue abstract class and implements the serializable interface. The abstractqueue abstract class implements the queue interface and encapsulates some general methods. I won't see more details.

Let's take a look at some of the attributes defined inside:

Construction method

It can be found that there are still many construction methods. Considering various situations, some default values are also given. The user can initialize according to the usage scenario.

In JDK, the root element is not deleted directly, and then the following elements are moved up to replenish the root element; Instead, find out the elements at the end of the team and delete them at the end of the team, then move down the root element to find a suitable position for the elements at the end of the team, and finally cover the following elements, so as to achieve the purpose of deleting the root element. In some cases, this will operate less steps than directly deleting the root element moved up, or directly moving the root element down, and then adjusting the position of the tail element (for example, the example in the above diagram, I don't believe you can try ^ ^).

After understanding the queue in and out operations of binary heap, other methods are relatively simple. Next, let's look at a more important process in binary heap, the structure of binary heap.

Heap construction

Clear all nodes in the priority queue. The event complexity of this operation is: O (n);

Reference article:

Source code analysis of PriorityQueue

Source code analysis of PriorityQueue