notes

Inheriting collection, based on dynamic array implementation, thread is not safe, cannot use NULL, insert elements must have comparator, queue features

The original

Note: The priority queue here is not a concept in a data structure, but a collection class in Java.

Note: IT is recommended to take a look at these two articles in the heap and comparator in my blog

Definition of a priority queue

  • A priority queue is a collection class that has a logical structure of a small root heap and a storage structure of a dynamic array (the capacity is automatically increased by one when the upper limit is reached).

The characteristics of priority queues

  • Priority queue elements must have priority!! Precedence is a “rule” of sequential order, meaning that classes inserted into the queue must implement an internal comparator or have an external comparator (as an argument in the constructor) ！！！！
  • A priority queue has all the characteristics of a small root heap.
  • Priority queues are not thread-safe.
  • Priority queues do not allow null elements.
  • The priority queue itself has an ordered (ascending from a[0] to a[n]) sequence, and the order of the extracted elements is an ordered sequence only if you take them out one by one. The reason is simple, the priority queue is a small root heap, that is, only the root node (a[0]) is guaranteed to be the smallest, the order of the rest of the elements is not guaranteed (of course, the other elements must obey the characteristics of the small root heap), when we fetch elements (poll), we can only fetch the elements of the root node, The last element of the heap is then cut to the root node (this extraction method is specified by the underlying algorithm to take full advantage of the characteristics of the heap), and then the heap is built for all remaining elements with the root node element remaining the smallest (second smallest in the original heap). The array traversed by the iterator of the priority queue is not sorted, just a small root heap. Array.sort (queue. Toarray), Array.sort (queue. Toarray, comparator), or some other sort method.
  • An insert in a priority queue (heap) can only be inserted at the end of the queue. Delete can only delete the first one.
  • Note: The priority of each element depends on the requirements of the problem. When an element is removed from the priority queue, multiple elements may have the same priority. In this case, the elements with the same priority are treated as a first-come, first-served queue and processed in the order in which they were enqueued.

Common methods:

Add (insert) :

public boolean add(E e)

View (only return root node element, not delete) :

public E peek()

Fetch (return the root node element, which removes the source data) :

public E poll()

Delete (if there are multiple identical elements, only the first one will be deleted) :

public boolean remove(Object o)

There are also some common methods in the Collection class, but I won’t go into that

Remember!! All methods that break the characteristics of the heap (such as insertion and deletion) will eventually be added to the source code to siftUp(I, e), so that the queue remains heap-like

Link: www.nowcoder.com/questionTer… Source: Niuke.com