The priority queue

Normal Queue: FIFO (Bank Queue)

First in, first out, elements are dequeued according to the order in which they entered the queue

Priority queue: It looks like a queue, the bottom layer is based on the implementation of the heap (doctors operate on patients, according to the condition, serious priority, the same condition, in order)

dynamicdequeue according to the size of the priority between elements

How is this different from sorting?

According to the sorted results in order

In terms of process scheduling of the operating system, the bottom layer is to maintain a priority queue.

Although the top is the maximum value, to delete the top element of the heap, the element shiftDown operation is also performed

Seeing the time complexity of logn level, it is almost certainly closely related to the "tree" structure.(It is not necessary to construct a binary tree here)

The recursive essential process of quicksort and merge is a "recursive" tree. Most of the backtracking algorithms are time complexity related to logn, and the essence of backtracking is also a tree.

The priority queue in JDK is the implementation of the minimum heap by default, and the first element of the queue is the minimum value in the current queue.

Compare size between elements

Compare two custom types for equality ->Override the equals method provided by the Object class!

Upcast:

The parameters are unified, and the parent class reference is used. No matter which subclass reference is used, the method that has been defined in the parent class can be called. The specific performance depends on the content of the subclass method overriding.-> Polymorphism

A naturally occurring is a relationship.Dog is an Animal.

The methods that can be called depend on the parent class. At this time, the reference is the reference of the parent class. Only the related methods defined in the parent class can be used.Who is called depends on whether the subclass has overridden it.If the subclass overrides it, the method overridden by the subclass must be called, otherwise the method of the parent class is called.

Downcast:

Subclass name Subclass reference = (subclass name) Parent class reference;//Force type conversion

Studnet stu = (Student) o;

If you want to call a method or attribute that is only available in the student class, you need to downcast, take off the coat referenced by the parent class, and restore it to the childclass reference.

At this time, we compare the studnet objects, and compare the name and age attributes in the student class. These two attributes are unique to the student, so we need to convert them down to the student.Quote.

Name and age are both privately modified attributes, why can they be accessed directly by reference here?

Because the overridden method is inside the student.

Comparing two custom objects which is bigger and which is smaller -> java.lang.Comparable

Once a class implements the Comparable interface, it means that the class has the ability to compare the size

int has three values ​​

Greater than 0: the current object is larger than the incoming object

Equal to 0: current object = incoming object

Less than 0: the current object is smaller than the incoming object

Once a custom class overrides the Comparable interface, sorting is ready!

Arrays.sort() defaults to descending order, I want ascending order, what should I do??

Let's change the compareTo method so that the larger is smaller, and the smaller is larger.

When you don't understand other people's code, the easiest way is to find an example and run it!Everything is solved easily~

Suppose now this sort needs to be sorted in ascending order of age sometimes, and sometimes in descending order of age, what should I do?

It is a taboo to frequently change the already written code according to different scenarios!

It may be possible to deceive yourself by changing it.

java.util.Comparator ->Comparator

The class that needs to be compared does not need to implement this interface, but there is a special class that implements this interface. This class is used to compare the size of students.

Comparator is more flexible than Comparable and requires no modification.To compare the code of the class -> non-invasive programming -> strategy mode (configure different comparators according to different needs)

It is to create a subclass of the Comparator interface, this subclass is only used once (anonymous inner class)

Anonymous inner class, the following is shorthand, also called Lambda expression, functional programming

Interview Question 17.14, Find the smallest K numbers in an array, and return the k numbers.

The minimum or maximum number** ---> are all priority queues (applications of the heap)

Take the big and use the small, take the small and use the big -->Find the smallest k number and construct the big root heap