catalogue
3.4 operation - out of queue (highest priority)
3.5 borrow heap to realize priority queue
2. See the previous section for the complete code of the heap
1. Priority queue
1.1 concept
In many applications, we usually need to deal with the objects according to the priority. For example, first deal with the object with the highest priority, and then deal with the object with the second highest priority. The simplest example is that when playing games on the mobile phone, if there is an incoming 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 internal principle
There are many ways to implement priority queues, but the most common is to build them using heaps.
1.3 operation - queue entry
Process (for example):
1.
First, put the array by tail interpolation
2.
Compare its value with that of its parents. If the value of its parents is large, it meets the nature of the heap and the insertion ends
3.
Otherwise, exchange the value of its parent position and repeat
2
,
3
step
4.
Up to the root node
Illustration:
3.4 operation - out of queue (highest priority)
In order to prevent the structure of the heap from being damaged, the top element of the heap is not directly deleted during deletion, but the last element of the array is used to replace the top element of the heap, and then the heap is readjusted by downward adjustment
3.5 borrow heap to realize priority queue
1. Implement an interface
public interface IQueue<E> {
// Join the team
void offer(E val);
//Out of the team
E poll();
//Returns the first element of the queue
E peek();
//Judge whether the queue is empty
boolean isEmpty();
}2. See the previous section for the complete code of the heap
3. Priority queue
/**
* Based on the priority queue of the largest heap, the higher the value, the higher the priority
* The team leader element is the element with the highest priority (the highest value)
*/
import stack_queue.queue.IQueue;
public class PriorityQueue implements IQueue<Integer> {
MaxHeap heap = new MaxHeap();
public PriorityQueue(){
heap = new MaxHeap();
}
@Override
public void offer(Integer val) {
heap.add(val);
}
@Override
public Integer poll() {
return heap.extractMax();
}
@Override
public Integer peek() {
return heap.peekMax();
}
@Override
public boolean isEmpty() {
return heap.isEmpty();
}
}3.6 testing
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueTest {
public static void main(String[] args) {
// Pass in the comparator through the construction method
// The default is the minimum heap. The smaller the value (the return value of the comparator compare), the higher the priority
// When a descending comparator is passed in, the value (the return value of comparator compare, the larger the value, the negative number will be returned)
// Queue<Student> queue = new PriorityQueue<>(new StudentComDesc());
// Queue<Student> queue = new PriorityQueue<>(new Comparator<Student>() {
// @Override
// public int compare(Student o1, Student o2) {
// return o2.getAge() - o1.getAge();
// }
// });
Queue<Student> queue = new PriorityQueue<>(new StudentCom());
Student stu1 = new Student(40,"Brother Ming");
Student stu2 = new Student(20,"Brother long");
Student stu3 = new Student(18,"Egg brother");
queue.offer(stu1);
queue.offer(stu2);
queue.offer(stu3);
while (!queue.isEmpty()){
System.out.println(queue.poll());
}
}
}
//Ascending (minimum heap)
class StudentCom implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.getAge() - o2.getAge();
}
}
//Descending (maximum heap)
class StudentComDesc implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.getAge() - o1.getAge();
}
}
class Student{
private int age;
private String name;
public int getAge() {
return age;
}
public Student(int age, String name) {
this.age = age;
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"age=" + age +
", name='" + name + '\'' +
'}';
}
}The results are as follows: Java heap & priority queue (Part I)
