What are the characteristics of queues?
First in, first out (FIFO).
In this paper, due to the details of the content is too much, so only part of the knowledge points sorted out a rough introduction, each small node there are more detailed content!
Recently compiled a data on algorithms. At the same time covered THE JVM, locks, concurrency, Java reflection, Spring principle, micro services, Zookeeper, database, data structure and a lot of knowledge points.
If you want to get this document for free, you can scan the image below
Into the queue:
The queue:
So, what does a priority queue look like?
Priority queues no longer follow a first-in, first-out principle, but are divided into two cases:
Maximum priority queue: Regardless of queue order, the current largest element is first queued.
Minimum priority queue: Regardless of the order in which the current smallest element is queued, the smallest element is queued first.
For example, if there is a maximum priority queue with the largest element 8, then element 8 is allowed to exit the queue first even though it is not the first element:
To meet the above requirements, it is not impossible to use linear data structure, but the time complexity is high, the worst time complexity O (n), is not the optimal way.
And you can think about why the worst time complexity is order n.
Let’s review the properties of binary heap:
1. The top of the largest heap is the largest element in the heap
2. The top of the smallest heap is the smallest element in the heap
Therefore, we can implement the maximum priority queue with the maximum heap, where each enqueue is an insert of the heap and each unqueue is a deletion of the top node of the heap.
Team entry operation:
1. Insert node 5
2. New node 5 floats to the proper position.
Queue operation:
1. Unqueue the top node 10 of the original heap
2. The last node 1 is replaced to the top of the heap
In this paper, due to the details of the content is too much, so only part of the knowledge points sorted out a rough introduction, each small node there are more detailed content!
Recently compiled a data on algorithms. At the same time covered THE JVM, locks, concurrency, Java reflection, Spring principle, micro services, Zookeeper, database, data structure and a lot of knowledge points.
If you want to get this document for free, you can scan the image below
3. Node 1 sinks and node 9 becomes the top of the heap
public class PriorityQueue {
private int[] array;
private int size;
public PriorityQueue(){
// The initial queue length is 32
array = new int[32];
}
/ * *
* team
* @param key join the team element
* /
private void enQueue(int key) {
// The queue length is out of the range
if(size >= array.length){
resize();
}
array[size++] = key;
upAdjust();
}
/ * *
* the team
* /
private int deQueue() throws Exception {
if(size <= 0){
throw new Exception(“the queue is empty !” );
}
// Get the top of the heap element
int head = array[0];
// The last element moves to the top of the heap
array[0] = array[–size];
downAdjust();
return head;
}
/ * *
* Float up adjustment
* /
private void upAdjust() {
int childIndex = size-1;
int parentIndex = childIndex/2;
// temp holds the value of the inserted leaf node for the final assignment
int temp = array[childIndex];
while (childIndex > 0 && temp > array[parentIndex])
{
// No real exchange, one-way assignment
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = parentIndex / 2;
}
array[childIndex] = temp;
}
/ * *
* Sinking adjustment
* /
private void downAdjust() {
// temp holds the parent value for the final assignment
int parentIndex = 0;
int temp = array[parentIndex];
int childIndex = 1;
while (childIndex < size) {
// If there is a right child and the value of the right child is greater than the value of the left child, locate the right child
if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
childIndex++;
}
// If the parent node is larger than any of the children, jump out
if (temp >= array[childIndex])
break;
// No real exchange, one-way assignment
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
/ * *
* Sinking adjustment
* /
private void resize() {
// The queue capacity doubles
int newSize = this.size * 2;
this.array = Arrays.copyOf(this.array, newSize);
}
public static void main(String[] args) throws Exception {
PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.enQueue(3);
priorityQueue.enQueue(5);
priorityQueue.enQueue(10);
priorityQueue.enQueue(2);
priorityQueue.enQueue(7);
System.out.println(” queue element: “+ priorityQueue.dequeue ());
System.out.println(” queue element: “+ priorityQueue.dequeue ());
}
}
The code uses arrays to store binary heap elements, so when the element exceeds the array range, resize is needed to expand the array length.
Through the above introduction, I believe you have a further understanding of the priority queue, I hope to help you!
In this paper, due to the details of the content is too much, so only part of the knowledge points sorted out a rough introduction, each small node there are more detailed content!
Recently compiled a data on algorithms. At the same time covered THE JVM, locks, concurrency, Java reflection, Spring principle, micro services, Zookeeper, database, data structure and a lot of knowledge points.
If you want to get this document for free, you can scan the image below
