PriorityQueue priority queue of Java collection framework

This article brings you relevant knowledge about java, which mainly introduces the relevant knowledge about PriorityQueue priority queue. The Java collection framework provides two types of priorities, PriorityQueue and PriorityBlockingQueue. Level queue, PriorityQueue is thread-unsafe, and PriorityBlockingQueue is thread-safe. Let’s take a look at it together. I hope it will be helpful to everyone.

Recommended study: "java Video Tutorial"

The Java collection framework provides two types of PriorityQueue and PriorityBlockingQueue The priority queue, PriorityQueue is thread-unsafe, and PriorityBlockingQueue is thread-safe. This article mainly introduces PriorityQueue

The relationship of priorityQueue in the Java collection framework is as follows:

1. Points to note when using PriorityQueue

1. When using it, 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 be compared in size, and objects that cannot be compared in size cannot be inserted, otherwise
ClassCastException## will be thrown.

#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 the internal capacity can be automatically expanded

5 . The

time complexity of inserting and deleting elements is log base 2 n

6. The bottom layer of PriorityQueue uses a heap data structure

7. PriorityQueue by default It is a small heap---that is, the elements obtained every time are the smallest elements (

If we want to turn it into a large heap, we need to re-compare the method. The default comparison method is the compareTo method in the Comparable interface)

2. Introduction to Common Interfaces of PriorityQueue

1. Construction of Priority Queue

Here are just a few common construction methods in

PriorityQueue, for others, you can refer to the help documentation.

ConstructorFunction introductionPriorityQueue()Create an empty Priority queue, PriorityQueue(intCreate a PriorityQueue(Collection extends E> c)
Use a collection to create a priority queue with Create a

2. Comparison of elements in PriorityQueue

After reading the construction method, let’s think about a question again

How does the priority queue achieve order? Because the priority queue is implemented with the help of a small root heap

In the process of implementing the small root heap, we know that a comparison of elements must occur, so the elements in the PriorityQueue must be able to compare in size. So how does PriorityQueue compare elements?

PriorityQueue adopts two methods:
Comparble and Comparator.

1. Comparble is the default internal comparison method . If the user inserts a custom type object, the object must implement the Comparble interface and override compareTo Method

2. Users can also choose to use a comparator object. If the user inserts a custom type object, a comparator class must be provided, and the class must implement the Comparator interface and override it. compare method.

We see that the program reports an error here, why? Because the Child object we inserted is not comparable ( does not implement the Comparable interface and does not use a custom comparator)

You can see

That is, we use the compareTo method in the Comparable interface, which is the default comparison method

At this time, let’s take a look at the error again Information

It seems that there is a problem when inserting elements into PriorityQueue

Then let’s open the source code of PriorityQueue and take a look (The following is the source code of the offer method in PriorityQueue)

Look at the source code of shiftUp again

Continue Click in siftUpComparable

At this time, let’s look back at the Child object we put in the PriorityQueue. It has no custom comparator and does not implement the Comparable interface. ,Of course an error is reported!

Okay then, let’s implement the Comparable interface in the Child class and compare by age

import java.util.PriorityQueue;
class Child implements Comparable<Child>{
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Child o) {
        return this.age - o.age;  // 默认实现小根堆
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

If you want to implement a large root heap, It’s easy to do

# Above we have implemented the Compable interface, so what if we customize an age comparator?

class Child {
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
class AgeComparator implements Comparator<Child> {

    @Override
    public int compare(Child o1, Child o2) {
        return o1.age - o2.age; // 实现小根堆
        // return o2.ae - o1.age 实现大根堆
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        AgeComparator ageComparator = new AgeComparator();
        // 创建具有默认初始容量的 PriorityQueue ，并根据指定的比较器对其元素进行排序。
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>(ageComparator);
        // 可以看到这里我的Child对象虽然没有实现Comparable接口，但因为我们对Child对象自定义了一个年龄比较器，所以插入元素不会报错
        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

3. Insert/delete/get the highest priority element

	The default capacity is 11
initialCapacity)	initial capacity is initialCapacity Priority queue, Note: initialCapacity cannot be less than 1, otherwise an IllegalArgumentException will be thrown Often
##PriorityQueue(Comparator comparator)Create a priority queue	default initial capacity and compare its elements against the specified comparator
PriorityQueue(int initialCapacity, Comparator comparator)	Initial capacity is initialCapacity's priority queue<strong></strong>, compares its elements according to the specified comparator Note: initialCapacity cannot be less than 1, otherwise IllegalArgumentException will be thrown Often

E peek()Get the element with the highest priority , if the priority queue is empty, return nullE poll()Remove the highest priority element and return, if the priority queue is empty, return nullint size()Get the number of valid elementsvoidClearCheck whether the priority queue is empty and return if empty true

Function Name	Function introduction
boolean offer(E e)	Insert element e, and return true if the insertion is successful, if the e object is empty , throwing NullPointerException, time complexity, note: when the space is not enough, it will be expanded
clear()
boolean isEmty()

Recommended learning: "

java video tutorial"

The above is the detailed content of PriorityQueue priority queue of Java collection framework. For more information, please follow other related articles on the PHP Chinese website!