1. Priority queue
1.1 concept
Queue is a first in, first out (FIFO) data structure. However, in some cases, the operation data may have priority. Generally, when leaving the queue, the elements with high priority may need to leave the queue first. In this scenario, using queue is obviously inappropriate. For example, when playing games on mobile phones, if there is a call, the system should give priority to the incoming call.
In this case, our data structure should provide two basic operations, one is to return the highest priority object, and the other is to add a new object.
This data structure is called priority queue
1.2 introduction to common interfaces
1.2.1 characteristics of PriorityQueue
Two types of priority queues, PriorityQueue and PriorityBlockingQueue, are provided in the Java collection framework. PriorityQueue is a line
The process is unsafe. PriorityBlockingQueue is thread safe. This article mainly introduces PriorityQueue
Pay attention when using
1. When using, you must import the package where PriorityQueue is located, that is:
import java.util.PriorityQueue;
2. The elements placed in the PriorityQueue must be able to compare the size, and cannot insert objects that cannot compare the size, otherwise they will be thrown
ClassCastException exception
3. null objects cannot be inserted, otherwise NullPointerException will be thrown
4. There is no capacity limit. You can insert any number of elements, and its internal capacity can be automatically expanded
5. The time complexity of inserting and deleting elements is
6. The bottom layer of PriorityQueue uses heap data structure. (Note: you can ignore what heap is here, which will be introduced later.)
7. PriorityQueue is a small heap by default -- that is, the smallest element is obtained every time
1.2.2 introduction to common interfaces of PriorityQueue
constructor | Function introduction |
PriorityQueue() | Create an empty priority queue with a default capacity of 11 |
PriorityQueue(int | Create a priority queue with an initial capacity of initialCapacity. Note: |
PriorityQueue(Collection<? | Create a priority queue with a collection |
1. Construction of priority queue
static void TestPriorityQueue(){
// Create an empty priority queue. The default capacity of the bottom layer is 11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
// Create an empty priority queue with the underlying capacity of initialCapacity
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
ArrayList<Integer> list = new ArrayList<>();
list.add(4);
list.add(3);
list.add(2);
list.add(1);
// Use the ArrayList object to construct an object of priority queue
// q3 already contains three elements
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());
System.out.println(q3.peek());
}Note: by default, the PriorityQueue queue is a small heap. If a large heap is required, the user needs to provide a comparator
// User defined Comparator: directly implement the Comparator interface, and then rewrite the compare method in the interface
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
p.offer(4);
p.offer(3);
p.offer(2);
p.offer(1);
p.offer(5);
System.out.println(p.peek());
}
} Function name | Function introduction |
boolean | Insert element E and return true after successful insertion. If the e object is empty, a NullPointerException exception is thrown |
E peek() | Get the element with the highest priority. If the priority queue is empty, return null |
E poll() | Remove the element with the highest priority and return it. If the priority queue is empty, return null |
int size() | Get the number of valid elements |
void | empty |
boolean | Check whether the priority queue is empty, and return true if it is empty |
static void TestPriorityQueue2(){
int[] arr = {4,1,9,2,8,0,7,3,6,5};
// In general, when creating priority queue objects, if you know the number of elements, it is recommended to directly give the underlying capacity
// Otherwise, little capacity expansion is required during insertion
// Capacity expansion mechanism: open up more space and copy elements, so the efficiency will be relatively low
PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
for (int e: arr) {
q.offer(e);
} S
ystem.out.println(q.size()); // Number of effective elements in the print priority queue
System.out.println(q.peek()); // Get the element with the highest priority
// Delete the sum of the two elements from the priority queue and get the element with the highest priority again
q.poll();
q.poll();
System.out.println(q.size()); // Number of effective elements in the print priority queue
System.out.println(q.peek()); // Get the element with the highest priority
q.offer(0);
System.out.println(q.peek()); // Get the element with the highest priority
// Delete the valid elements in the priority queue and check whether they are empty
q.clear();
if(q.isEmpty()){
System.out.println("Priority queue is empty!!!");
} e
lse{
System.out.println("Priority queue is not empty");
}
}Note: the following is the capacity expansion method of PriorityQueue in JDK 1.8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}Description of priority queue expansion:
If the capacity is less than 64, it is expanded by twice the oldCapacity
If the capacity is greater than or equal to 64, it is expanded by 1.5 times the oldCapacity
If the capacity exceeds MAX_ARRAY_SIZE, according to MAX_ARRAY_SIZE for capacity expansion
1.3 application of priority queue (key)
top-k problem: the largest or smallest top k data. For example, the world's top 500 companies
class Solution {
public int[] smallestK(int[] arr, int k) {
// Parameter detection
if(null == arr || k <= 0)
return new int[0];
PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
// Put the elements in the array into the heap in turn
for(int i = 0; i < arr.length; ++i){
q.offer(arr[i]);
} /
/ Put the top of the priority queue k Put elements into the array
int[] ret = new int[k];
for(int i = 0; i < k; ++i){
ret[i] = q.poll();
} r
eturn ret;
}
}2. Simulation implementation of priority queue
The underlying PriorityQueue in JDK1.8 uses the data structure of the heap, and the heap actually adjusts some elements on the basis of a complete binary tree.
2.1 concept of reactor
If there is a key set K = {k0, k1, k2,..., kn-1}, store all its elements in a complete binary tree
In a one-dimensional array, and satisfy: ki < = k2i+1 and Ki < = k2i+2 (KI > = k2i+1 and Ki > = k2i+2) I = 0, 1, 2..., it is called a small heap (or large
Heap). The heap with the largest root node is called the maximum heap or the large root heap, and the heap with the smallest root node is called the minimum heap or the small root heap.
Nature of heap:
The value of a node in the heap is always not greater than or less than the value of its parent node;
Heap is always a complete binary tree.
2.2 storage mode of heap
According to the concept of heap, heap is a complete binary tree, so the rules of sequence can be stored in a sequential manner,
Note: for incomplete binary trees, it is not suitable to use sequential storage, because in order to restore the binary tree, empty sections must be stored in the space
Point, which will lead to low space utilization.
After storing the elements in the array, the tree can be restored according to the property 5 of the binary tree chapter. Assuming i is the subscript of the node in the array, there are:
If i is 0, the node represented by i is the root node; otherwise, the parent node of node i is (i - 1)/2
If 2 * i + 1 is less than the number of nodes, the left child subscript of node i is 2 * i + 1, otherwise there is no left child
If 2 * i + 2 is less than the number of nodes, the subscript of the right child of node i is 2 * i + 2, otherwise there is no right child
Example
1.The following keyword sequence is heap:() A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60 D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 F: 50,100,70,65,60,32 2.Known small root heap is 8,15,10,21,34,16,12，After deleting keyword 8, the heap needs to be rebuilt. In this process, the number of comparisons between keywords is() A: 1 B: 2 C: 3 D: 4 3.A group of record sorting codes are(5 11 7 2 3 17),Then the initial heap established by using the heap sorting method is() A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5) D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5) 4.Minimum heap[0,3,2,5,7,4,6,8],After deleting the heap top element 0, the result is() A: [3，2，5，7，4，6，8] B: [2，3，5，7，4，6，8] C: [2，3，4，5，7，8，6] D: [2，3，4，5，6，7，8] [Reference answer] 1.A 2.C 3.C 4.C
2.3 heap creation
2.3.1 stack down adjustment
For the data in the set {27,15,19,18,28,34,65,49,25,37}, what if we create it into a heap?
After careful observation of the above figure, it is found that the left and right subtrees of the root node have fully satisfied the nature of the heap, so you only need to adjust the root node downward.
Downward process (taking small heap as an example):
1. Let the parent mark the node that needs to be adjusted, and the child mark the left child of the parent (Note: if the parent has children, it must have left children first)
2. If the left child of the parent exists, that is: child < size, carry out the following operations until the left child of the parent does not exist
Whether the right child of the parent exists. Find the youngest child of the left and right children and let the child mark
Compare the parent with the younger child if:
The parent is smaller than the younger child, and the adjustment is over
Otherwise: exchange the parent with the child of the younger child. After the exchange is completed, the large element in the parent moves downward, which may lead to the child
The tree does not satisfy the nature of the pair, so it needs to continue to adjust downward, that is, parent = child; child = parent*2+1; Then continue 2
public void shiftDown(int[] array, int parent) {
// Child marks the left child of the parent first, because the parent may be right, left or not right
int child = 2 * parent + 1;
int size = array.length;
while (child < size) {
// If the right child exists, find the smaller one of the left and right children and mark it with child
if(child+1 < size && array[child+1] < array[child]){
child += 1;
} /
/ If the parents are younger than their youngest child, it means that the structure has met the characteristics of heap
if (array[parent] <= array[child]) {
break;
}else{
// Swap parents for younger children
int t = array[parent];
array[parent] = array[child];
array[child] = t;
// Moving down the large elements in the parent may cause the subtree to not meet the nature of the heap, so it needs to continue to adjust downward
parent = child;
child = parent * 2 + 1;
}
}
}Note: when adjusting a binary tree with a parent as the root, you must satisfy that the left and right subtrees of the parent are already heaped before you can adjust downward.
Time complexity analysis:
The worst case is the case shown in the figure. The number of comparisons from root to leaf is the height of the complete binary tree, that is, the time complexity is Olog2n
2.3.2 heap creation
Then how to adjust the ordinary sequence {1,5,3,8,7,6}, that is, the left and right subtrees of the root node do not meet the characteristics of the heap
public static void createHeap(int[] array) {
// Find the penultimate non leaf node, starting from the position of the node and going forward to the root node. If you encounter a node, apply downward adjustment
int root = ((array.length-2)>>1);
for (; root >= 0; root--) {
shiftDown(array, root);
}
}2.3.3 time complexity of reactor construction
Because the heap is a complete binary tree, and the full binary tree is also a complete binary tree, the full binary tree is used here for simplification (the time complexity is originally seen as
Approximate value, more nodes do not affect the final result):
Therefore, the time complexity of reactor building is O(N)
2.4 heap insertion and deletion
2.4.1 heap insertion
There are two steps to insert the heap:
1. Put the elements into the bottom space first (Note: when the space is insufficient, it needs to be expanded)
2. Adjust the last newly inserted node upward until it meets the nature of the heap
public void shiftUp(int child) {
// Find child's parents
int parent = (child - 1) / 2;
while (child > 0) {
// If the parents are older than the children, and the parents meet the nature of the heap, the adjustment is over
if (array[parent] > array[child]) {
break;
} e
lse{
// Exchange parent and child nodes
int t = array[parent];
array[parent] = array[child];
array[child] = t;
// When small elements move down, it may be that the value subtree does not meet the nature of pairs, so it needs to continue to increase upward
child = parent;
parent = (child - 1) / 1;
}
}
}2.4.2 deletion of heap
Note: deleting the heap must delete the top element of the heap. The details are as follows:
1. Exchange the top element of the heap with the last element in the heap
2. Reduce the number of valid data in the heap by one
3. Adjust the top element downward
2.5 using heap simulation to realize priority queue
public class MyPriorityQueue {
// Demo function, no longer consider the code of the expansion part
private int[] array = new int[100];
private int size = 0;
public void offer(int e) {
array[size++] = e;
shiftUp(size - 1);
}
public int poll() {
int oldValue = array[0];
array[0] = array[--size];
shiftDown(0);
return oldValue;
}
public int peek() {
return array[0];
}
}