Java has some knowledge about priority queue and map / set

Suunsr 2022-05-22 12:26:30 阅读数:224


One : Priority queue

Priority column : Queue up dynamically according to the size of the elements , The number of elements processed by the priority queue changes dynamically , In and out , Unlike sorting, the number of sets processed is fixed .

JDK The priority queue in is the smallest heap by default , So we need to modify compareTo Method .

Sometimes in different scenes , There are requirements for ascending and descending order , It is a taboo to frequently modify the written code according to different scenarios , So we use Comparator The comparator .

Comparator The comparator : Classes that need to be compared do not need to implement this interface , Instead, there is a special class to implement this interface , This class is used for size comparison . Use Comparator Speaking of JDK The minimum heap is transformed into the maximum heap

It is usually encountered before selecting from a pile of data ** Number , Apply heap to solve problems ( Take the big and use the small , Take the small and use the large )

Heap sort :

Take the largest heap as an example , Take out the maximum value in turn until the heap is empty , Get a descending array => Cannot sort on the original array , You also have to create a heap with the same size as the current array => Spatial complexity O(N)

1. Any array can heapify => Adjust to maximum heap size

i = arr.length;i>0;i++

2. Traverse the maximum heap again ,swap(0,i) => Every time I do swap operation , Exchange the maximum value of the current heap to the final position .

Two :Map/Set

set : Store non duplicate key value , Use set Collection for de reprocessing

map: What's stored is key==value Key value pair , If necessary, according to key Find the corresponding value Use map aggregate

stay HaspMap in , The insertion order of elements has nothing to do with the order after saving , If necessary, insert and save in the same order , Use LinkedHashMap

1.HashMap It's based on a hash table + The structure of the red black tree (JDK8 after ),HashMap The order in which the elements are saved is independent of the insertion order ,key and value Can be null;

2.TreeMap It is based on the structure of red black tree ,TreeMap The saving order of elements is also independent of the insertion order of elements ,key Not for null,value It can be for null. Use TreeMap When saving elements , Element must be Comparable Subclass or pass in comparator .

3.LinkedHahMap Is in the HashMap A linked list is maintained to record the insertion sequence of elements , You can save elements in the order they are inserted .

Set aggregate : duplicate removal

Traverse set aggregate , Use it directly for-each Circulation is enough .

Traverse map When we gather , Need to put Map->Set Conduct for-each Traverse ,for(Map.entry< The specific type > entry:map.entrySet())

copyright:author[Suunsr],Please bring the original link to reprint, thank you.