Welcome to pay attention to the public account “JAVA Front” to view more wonderful sharing articles, mainly including source code analysis, practical application, architecture thinking, workplace sharing, product thinking and so on, at the same time, welcome to add my personal wechat “JAVA_front” to communicate and learn together
1 Priority queue applications
A queue is a first-in, first-out data structure in which the first element put into the queue is dequeued first. But there is a scenario where we want to de-queue not according to the order in which the element is put into the queue, but according to the priority of the element itself. For example, if the element has a higher priority, it will be de-queued first, and then we use priority queues.
1.1 the application a
We imagine a message sending business scenario where messages have priority attributes and messages with higher priority are sent in the same queue, with priority defined as follows:
// Priority P1 > P2 > p3
public enum PriorityEnum {
P1(1."Priority 1"),
P2(2."Priority 2"),
P3(3."Priority 3"); }Copy the codeThe message object is defined as follows:
public class MyMessage implements Comparable {
/** * Message priority */
private int priority;
/** * Message content */
private String messge;
public MyMessage(int priority, String message) {
this.priority = priority;
this.messge = message;
}
@Override
public int compareTo(Object obj) {
MyMessage message = (MyMessage) obj;
return this.priority - message.priority; }}Copy the codeJava.util. PriorityQueue can do the following:
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue<MyMessage> messageQueue = new PriorityQueue<MyMessage>();
MyMessage m1 = new MyMessage(PriorityEnum.P1.getCode(), "message1");
MyMessage m2 = new MyMessage(PriorityEnum.P2.getCode(), "message2");
MyMessage m3 = new MyMessage(PriorityEnum.P3.getCode(), "message3");
messageQueue.offer(m3);
messageQueue.offer(m1);
messageQueue.offer(m2);
while (messageQueue.size() > 0) { System.out.println(messageQueue.poll()); }}}Copy the codeCode execution result:
send message=MyMessage(priority=1, messge=message1)
send message=MyMessage(priority=2, messge=message2)
send message=MyMessage(priority=3, messge=message3)
Copy the codePriorityQueueTest The order in which messages are placed in the priority queue:
Three, one, twoCopy the codePriorityQueueTest gets the order of messages from the priority queue:
One, two, threeCopy the code
1.2 application 2
Now the message priority is business changed:
// Priority P3 > P2 > P1
public enum PriorityEnum {
P1(1."Priority 1"),
P2(2."Priority 2"),
P3(3."Priority 3"); }Copy the codeThe expected output sequence is as follows:
Three, two, oneCopy the codeTo achieve the desired output order, the code changes as follows:
public class MyMessage implements Comparable {
@Override
public int compareTo(Object obj) {
MyMessage message = (MyMessage) obj;
return message.priority - this.priority; // The comparison relationship changes}}Copy the code
2 binary heap
In the first chapter, we saw that PriorityQueue can output elements in order of priority. What is the underlying mechanism? The answer is binary heap.
2.1 What is binary heap
The binary heap is divided into the big top heap and the small top heap. We first look at the big top heap. From the following figure, we can see that the maximum value of the whole tree is at the root node, so it is called the big top heap:
Let’s look at the small top heap. From the following figure, we can see that the minimum value of the whole tree is at the root node, so it is called the small top heap:
2.2 How to Store binary Heap
Binary heaps look complicated, but can actually be represented by arrays. Let’s take the big top heap as an example:
The first step is to declare an array of length 10, since the binary tree has 10 nodes:
int[] array = new int[10]
Copy the codeStep 2 Set the root node 100 as the first element of the array:
array[0] = 100
Copy the codeStep 3 Set all nodes to the corresponding positions in the array:
leftChildIndex = (parentIndex * 2) + 1
rightChildIndex = (parentIndex * 2) + 2
Copy the codeFor example, if we set 90 to the corresponding position in the array, the index of the parent node 100 is 0, and 90 is the left child of 100:
parentIndex = 0
leftChildIndex = (0 * 2) + 1 = 1
array[1] = 90
Copy the codeFor example, set 80 to the corresponding position in the array, where the parent node 100 has an index equal to 0 and 80 is the right child of 100:
parentIndex = 0
leftChildIndex = (0 * 2) + 2 = 2
array[2] = 80
Copy the codeFor example, if we set 30 to the corresponding position in the array, the index of the parent 80 is equal to 2, and 30 is the right child of 80:
parentIndex = 2
leftChildIndex = (2 * 2) + 2 = 6
array[6] = 30
Copy the codeIf we know the index of the child node array, we can also invert the index of the parent node:
parentIndex = (childIndex - 1) / 2
Copy the codeFor example, if the index of node 30 is 6, then the index of its parent node 80 is 2:
childIndex = 6
parentIndex = (6 - 1) / 2 = 2
Copy the code
2.3 New Elements
Now add node 92 to the binary heap. The first step is to insert this element at the last index position of the array:
This clearly does not meet the basic requirements of binary heap, need to loop with the parent node to compare, if found to be larger than the parent node swap places, otherwise exit the loop. In the first round, 92 is greater than 60, and the two switch places:
In the second round, 92 is greater than 90, and the two switch positions:
In the third round, 92 is less than 100, no need to swap and exit the cycle:
The last node, 92, starts at the end and moves up to the corresponding position through the comparison cycle. This process is called SiftUp, which can be understood as rising.
2.4 Get and delete the heaptop element
Which element of the tree is most valuable to the business? The top of the heap element, no doubt. Taking the big top heap as an example, the maximum value is always at the top of the heap, which can be understood as the element with the highest priority is always at the top of the heap. As long as the top element is recycled, processing can be achieved according to the priority order.
When the top of the heap element is acquired, it needs to be removed, which may involve binary heap element position change. Here is the process:
The second round removes the last element, 60, from its original position and sets it to the top of the heap:
In the third round, 60 is compared with the left and right child nodes 92 and 80, and 92, the larger child node, is selected, and the position of 92 is greater than 60 is exchanged:
In the fourth round, 60 is compared with the left and right child nodes 40 and 90, and the larger child node 90 is selected, and 90 is greater than 60, and the two switch positions:
In the fifth round, 60 is compared with the left child node 50, when 50 is less than 60, there is no need to swap and exit the cycle:
The last node, 60, first moves to the root node, and then moves down to the corresponding position through cyclic comparison. We call this process SiftDown, which can be understood as sinking.
3 Handwritten big top stack
After the analysis in the second chapter, we know that the most important methods of binary heap are adding elements and obtaining and deleting the top elements of the heap, among which SiftUp and SiftDown are the two most important processes.
3.1 Interface Declaration
public interface IMaxHeap<E extends Comparable> {
/** * New element **@paramElement Element to be added *@returnTrue indicates success */
public boolean offer(E element);
/** * gets and deletes the heaptop element **@returnThe maximum * /
public E getAndRemoveTop(a);
/** * heap size **@returnThe heap size * /
public int size(a);
}
Copy the code
3.2 Big top heap implementation
public class MyMaxHeap<E extends Comparable> implements IMaxHeap<E> {
private ArrayList<E> array;
public MyMaxHeap(a) {
array = new ArrayList<E>();
}
@Override
public boolean offer(E element) {
// 1. Add to the end of the array
int lastIndex = size();
array.add(lastIndex, element);
// 2.siftUp
siftUp(lastIndex);
return Boolean.TRUE;
}
@Override
public E getAndRemoveTop(a) {
// 1. The root node is the maximum
E max = array.get(0);
// 2. Finally, the node is moved to the root node and deleted
int lastIndex = size() - 1;
E lastNode = array.get(lastIndex);
array.set(0, lastNode);
array.remove(lastIndex);
// 3.siftDown
siftDown(0);
// 4. Return the maximum value
return max;
}
@Override
public int size(a) {
return array.size();
}
// The node floats
private void siftUp(int currentIndex) {
// The root node does not float
while(currentIndex ! =0) {
// The current node
E currentValue = array.get(currentIndex);
/ / the father index
int parentIndex = getParentIndex(currentIndex);
/ / the parent node
E parentValue = array.get(parentIndex);
// If the current node is smaller than the parent node, exit the loop
if (currentValue.compareTo(parentValue) < 0) {
break;
}
// If the current node is greater than or equal to the parent node, swap positionsarray.set(parentIndex, currentValue); array.set(currentIndex, parentValue); currentIndex = parentIndex; }}// The node sinks
private void siftDown(int currentIndex) {
// The current node has no left child
while (getLeftChildIndex(currentIndex) < size()) {
// The current node
E currentValue = array.get(currentIndex);
// Left subindex
int leftChildIndex = getLeftChildIndex(currentIndex);
// Left child node
E leftChildValue = array.get(leftChildIndex);
// Right subindex
Integer rightChildIndex = null;
E rightChildValue = null;
if (getRightChildIndex(currentIndex) < size()) {
rightChildIndex = getRightChildIndex(currentIndex);
rightChildValue = array.get(rightChildIndex);
}
// The right child node exists
if (null! = rightChildIndex) {// Find the larger child nodes
int biggerIndex = rightChildIndex;
if (leftChildValue.compareTo(rightChildValue) > 0) {
biggerIndex = leftChildIndex;
}
// The larger node is smaller than the current node and exits the loop
E biggerValue = array.get(biggerIndex);
if (biggerValue.compareTo(currentValue) < 0) {
break;
}
// A larger node is greater than or equal to the current node
array.set(currentIndex, biggerValue);
array.set(biggerIndex, currentValue);
currentIndex = biggerIndex;
}
// The right child does not exist
else {
// If the left child is smaller than the current node, exit the loop
if (leftChildValue.compareTo(currentValue) < 0) {
break;
}
// If the left child node is greater than or equal to the current node, swap placesarray.set(currentIndex, leftChildValue); array.set(leftChildIndex, currentValue); currentIndex = leftChildIndex; }}}// Get the index of the left child node
private int getLeftChildIndex(int currentIndex) {
return currentIndex * 2 + 1;
}
// Get the right child index
private int getRightChildIndex(int currentIndex) {
return currentIndex * 2 + 2;
}
// Get the parent node index
private int getParentIndex(int currentIndex) {
if (currentIndex == 0) {
throw new RuntimeException("root node has no parent");
}
return (currentIndex - 1) / 2;
}
public ArrayList<E> getArray(a) {
return array;
}
public void setArray(ArrayList<E> array) {
this.array = array; }}Copy the code
3.3 Code Testing
public class MyMaxHeapTest {
public static void main(String[] args) {
MyMaxHeap<Integer> maxHeap = new MyMaxHeap<Integer>();
maxHeap.offer(70);
maxHeap.offer(90);
maxHeap.offer(80);
maxHeap.offer(100);
maxHeap.offer(60);
System.out.println("maxHeap test offer, heapInfo=" + maxHeap.getArray());
Integer maxValue = maxHeap.getAndRemoveTop();
System.out.println("maxHeap test getAndRemoveTop, maxValue=" + maxValue + ", heapInfo="+ maxHeap.getArray()); }}Copy the codeCode execution result:
maxHeap test offer, heapInfo=[100, 90, 80, 70, 60]
maxHeap test getAndRemoveTop, maxValue=100, heapInfo=[90, 70, 80, 60]
Copy the code
4 Handwritten priority queue
We wrote the big top heap in Section 3, so the handwritten priority queue is simple, just declare a queue to encapsulate the big top heap and provide queue-specific access methods.
4.1 Interface Declaration
public interface IPriorityQueue<E extends Comparable> {
/** * New element **@param* / element element
public void offer(E element);
/** * gets the first element **@returnThe first element * /
public E poll(a);
/** * get the queue length **@returnQueue length */
public int size(a);
}
Copy the code
4.2 Priority queue implementation
public class MyPriorityQueue<E extends Comparable> implements IPriorityQueue<E> {
private MyMaxHeap<E> myMaxHeap;
public MyPriorityQueue(a) {
myMaxHeap = new MyMaxHeap<E>();
}
@Override
public void offer(E element) {
myMaxHeap.add(element);
}
@Override
public E poll(a) {
return myMaxHeap.getAndRemoveTop();
}
@Override
public int size(a) {
returnmyMaxHeap.size(); }}Copy the code
4.3 Code Test
public class PriorityQueueTest {
public static void main(String[] args) {
MyPriorityQueue<Integer> myPriorityQueue = new MyPriorityQueue<Integer>();
myPriorityQueue.offer(10);
myPriorityQueue.offer(30);
myPriorityQueue.offer(20);
while (myPriorityQueue.size() > 0) { System.out.println(myPriorityQueue.poll()); }}}Copy the codeCode execution result:
30
20
10
Copy the code
5 Source code Analysis
5.1 PriorityQueue
We see that siftUp is performed in the offer method, where the rule is that the current node is smaller than the parent node, and siftDown is performed in the poll method, where the current node is larger than the child node, and the position is changed.
These two rules represent the use of a small top heap and can explain the application of an output sequence in Section 1. We are applying two change object comparison rules, exchange comparison order, so we can achieve the big top heap function.
package java.util;
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
public PriorityQueue(a) {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
// Add a new element
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
/ / to rise
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if(comparator ! =null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
/ / the father index
int parent = (k - 1) > > >1;
/ / the parent node
Object e = queue[parent];
// If the current node is greater than or equal to the parent node, exit the loop
if (key.compareTo((E) e) >= 0)
break;
// If the current node is smaller than the parent node, the swap position floats up
queue[k] = e;
k = parent;
}
queue[k] = key;
}
// Get and delete the header element
public E poll(a) {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if(s ! =0)
/ / sink
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if(comparator ! =null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
while (k < half) {
// Left subindex
int child = (k << 1) + 1;
// Left child node
Object c = queue[child];
// Right subindex
int right = child + 1;
// Compare the left and right child nodes to larger nodes
if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
// If the current node is smaller than or equal to a larger node, exit the loop
if (key.compareTo((E) c) <= 0)
break;
// If the current node is larger than a larger node, the swap position sinksqueue[k] = c; k = child; } queue[k] = key; }}Copy the code
5.2 DelayQueue
The bottom layer of delay queue uses priority queue. The priority indicator is based on the time attribute of the element itself. The closer the new element is to the head of the queue, the earlier the element expires.
When fetching the top element, the element getDelay method is first called, usually the element time minus the current time, if the element time is less than or equal to the current time, indicating that the element has expired, fetching and deleting the first element.
package java.util.concurrent;
public class DelayQueue<E extends Delayed> extends AbstractQueue<E> implements BlockingQueue<E> {
private final transient ReentrantLock lock = new ReentrantLock();
private final PriorityQueue<E> q = new PriorityQueue<E>();
public boolean offer(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
q.offer(e);
if (q.peek() == e) {
leader = null;
available.signal();
}
return true;
} finally{ lock.unlock(); }}public E poll(a) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
// Get the first element
E first = q.peek();
// If the queue header element time is greater than the current time, it is not due
if (first == null || first.getDelay(NANOSECONDS) > 0)
return null;
// The time of the first element is less than or equal to the current time
else
return q.poll();
} finally{ lock.unlock(); }}}Copy the code
6 Article Summary
First, this paper uses java.util.PriorityQueue to demonstrate the function. From application ONE, it can be seen that it uses a small top heap by default. From application two, it can be seen that the effect of a large top heap can be achieved after changing the object comparison relationship.
The second paper introduces the concepts related to binary heap. Binary heap is divided into big top heap and small top heap. The two most important methods are adding elements and acquiring and deleting top elements of the heap.
In the third paper, the big top heap and priority queue are written, in which the big top heap is the most important to deal with the two processes of rising and sinking, and the priority queue is encapsulated on the basis of the big top heap.
Fourth, this paper analyzes the source code of PriorityQueue and DelayQueue, in which the PriorityQueue uses the small top heap by default, and the DelayQueue uses the PriorityQueue at the bottom, and the priority indicator is time. I hope this paper will be helpful to you.
Welcome to pay attention to the public account “JAVA Front” to view more wonderful sharing articles, mainly including source code analysis, practical application, architecture thinking, workplace sharing, product thinking and so on, at the same time, welcome to add my personal wechat “JAVA_front” to communicate and learn together