To implement a minimum priority queue with PriorityBlockingQueue, consider the following aspects: expansion, joining, and leaving
PriorityBlockingQueue implements heap sort internally with arrays.
The graph is at the end, so if the code doesn't make sense, look at the graph
Heap sort
1.1 Heap sort concept
The minimum heap is a completely sorted binary tree in which the data value of any non-terminal node is not greater than the value of its left and right children
** In other words: **
- 1, array to achieve binary tree, so meet the characteristics of binary tree
- 2. The root element is the smallest element, and its parent node is smaller than its two children
- 3. The elements in a tree are relatively ordered
1.2 How to achieve relatively orderly heap
Insert element, the back of the inserted into the last element of the array, and then compared with the parent node of the node size, if the inserted element is less than the parent node element, then the parent node exchange position, then insert element exchange to the parent node location, and compared with the node’s parent, until is greater than the parent element or reach the roof, This process is called buoyancy, or floating during insertion.
sinking
PriorityBlockingQueue Queue
2.1 PriorityBlockingQueue. Offer
public boolean offer(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
int n, cap;
Object[] array;
// 1. Before joining the team, determine whether to expand the capacity
while ((n = size) >= (cap = (array = queue).length))
tryGrow(array, cap);
try {
Comparator<? super E> cmp = comparator;
if (cmp == null)
// 2. Data is queued
siftUpComparable(n, e, array);
else
siftUpUsingComparator(n, e, array, cmp);
// 3.size Records the number of valid elements in the current array
size = n + 1;
notEmpty.signal();
} finally {
lock.unlock();
}
return true;
}
Copy the code1. Check whether the current array needs to be expanded before joining the team
2, size is the number of elements in the array
2.2 PriorityBlockingQueue.siftUpComparable
private static <T> void siftUpComparable(int k, T x, Object[] array) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
int parent = (k - 1) > > >1;
Object e = array[parent];
// compareTo is implemented by x, if the calculation method is return x.priority -e.priority, it is the smallest heap
// The queue with the lowest priority value goes first
if (key.compareTo((T) e) >= 0)
break;
array[k] = e;
k = parent;
}
array[k] = key;
}
Copy the codeHere is the calculation: First, insert the joining element to the end of the array, and then obtain the index value of the element’s parent node. The definition rule of the parent node is the index value of the current element in the array (index -1 >>> 1), compare the joining element with its parent node, compareTo < 0, then replace the parent node. After the sequential swap is complete, continue to traverse the comparison up in this manner.
Remark:
Three, out of the team
3.1 to dequeue
private E dequeue(a) {
int n = size - 1;
if (n < 0)
return null;
else {
Object[] array = queue;
E result = (E) array[0];
E x = (E) array[n];
array[n] = null;
Comparator<? super E> cmp = comparator;
if (cmp == null)
// x: the last element of the array
siftDownComparable(0, x, array, n);
else
siftDownUsingComparator(0, x, array, n, cmp);
size = n;
returnresult; }}Copy the code3.2 siftDownComparable
T x corresponds to the last element in the array
private static <T> void siftDownComparable(int k, T x, Object[] array,
int n) {
if (n > 0) {
Comparable<? super T> key = (Comparable<? super T>)x;
// 2. Initialize half as the parent of element x
int half = n >>> 1;
while (k < half) {
// select the left child of the current node (the first time is the root node)
int child = (k << 1) + 1;
// 4. Assign the value of the left child of the current node to Object C
Object c = array[child];
// 5. Select the index of the right child node
int right = child + 1;
if (right < n &&
((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
// 6. If the left child is > the right child, the value of the right child is assigned to Object C
c = array[child = right];
if (key.compareTo((T) c) <= 0)
// 7. If the value of the last node is less than the value of the left and right child nodes, the operation is complete
break;
// 8. After the last element is moved to the top of the heap, it is compared with the smaller of its children
array[k] = c;
// 9. Continue traversing down
k = child;
}
// 10. At the end of the loop, place the value of the last element in the specified positionarray[k] = key; }}Copy the codeSimply look at the code, look at the text is very confused, draw a picture to facilitate future review
Iv. Flow chart
Before you look at the figure below, one thing to understand is that the array structure is the actual structure of the elements in PriorityBlockingQueue. The binary tree is just a mapping of the array
4.1 Structure diagram of array implementation minimum heap
5. Flow chart of team entry
** Uses an array to implement the minimum heap. Although the queue is ordered and the minimum value is first queued, the array itself is not an ordered array
Inserts an element of value 1 into the array
5.1 Val (1) corresponds to index(13)
Insert val(1) at the end of the array, corresponding to index = 13
5.2 Comparison between Val (1) and index(6)
Index value of parent node parentIndex = 6, corresponding to val(12), compare val(1) with val(12), find that val(1) is smaller than val(12), replace the position of val(1) and val(12), after replacement val(1) corresponds to index(6).
After replacement, the figure is as follows:
5.3 Comparison between Val (1) and index(2)
Val (1) and val(12) swap positions, val(1) corresponds to index = 6, parentIndex = 2, val(10) < val(10), val(1) and val(10) swap positions, val(1) corresponds to index = 6, parentIndex = 2, val(10) < val(10). Val of 1 corresponds to index of 2.
After replacement, the figure is as follows:
5.4 Compare val(1) with index(0)
Val (1) < val(2); val(10) < val(2); val(1) < val(2); val(10) < val(2); val(10) < val(2); So val(1) swaps with val(2), and val(1) corresponds to index(0).
After replacement, the figure is as follows:
5.5 Val (1) team entry completed
Six, team flow chart
The element of the root node is always the smallest element, and corresponds to index(0). The queue takes the index(0) element, and then places the end element of the value at index(0), and then compares it with its child nodes in turn
6.1 Taking the Index (0) element
6.2 The val(12) element is placed at index(0)
Place the trailing element at index(0) and the last element of the array val = 12, which moves val(12) from index(13) to the root node index(0)
After the move, the picture is as follows:
6.3 Compare val(12) with index(1) and index(2)
ChildIndex (0) = childIndex(1); childIndex(2) = childIndex(2); Val (12) > val(2), replace val(12) with val(2), index = 2
After replacement, the figure is as follows:
6.4 Compare val(12) with index(5) and index(6)
The left and right child nodes of index(2) are childIndex(5), childIndex(6), corresponding values are val(11), val(10), val(11) > val(10), Val (12) = childIndex(10); val(12) = childIndex(10); val(12) = childIndex(10)
After replacement, the figure is as follows:
6.5 End of team exit
After a queue operation, the current array structure looks like the figure below
