1. What is the priority queue??

First, the priority queue is a queue. It also has all the properties of the queue.

Secondly, the priority queue takes out the element with the highest priority every time.

The interior of the priority queue is maintained by heap. Put the highest priority first.

2. When will this queue be used??

After reading the definition of priority queue, you seem to understand it or not. This queue, what do you use it for?

1) Objects to sort and objects to compare when sorting

In common sorting methods (insert, quick sort, etc.), the sorted objects are the same as the comparison objects, and are sorted according to the size of the number itself.

Priority queue can sort objects that are the same as the comparison objects, or sort objects that are different from the comparison objects.

One case where the sorted objects are different from the objects compared during sorting is to sort the Map. In the Map, sort the keys by the Value value. At this time, the sorting object is Key and the comparison object is Value.

2) Pile

The interior of the priority queue is maintained by heap. Therefore, the priority queue can also be used as a heap. When you need to use the heap, try using the priority queue.

3. Sort an array

int[] arr = {3, 7, 5, 1, 8};
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int t : arr) {
    queue.offer(t);
    System.out.println("queue = " + queue);
}

Output results:

queue = [3]
queue = [3, 7]
queue = [3, 7, 5]
queue = [1, 3, 5, 7]
queue = [1, 3, 5, 7, 8]

As can be seen from queue = [3, 7, 5], although the queue is also arranged according to the natural order of integers, it is not arranged in an increasing order (the elements in the queue are not always arranged in an increasing order) and is stored in a heap.

Next, set the size of the priority queue to 3 to see the change of the priority queue

int[] arr = {3, 7, 5, 1, 8};
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int cur : arr) {
    queue.offer(cur);
    if (queue.size() > 3){
        int t = queue.poll();
        System.out.print("poll = " + t);
    }
    System.out.println("queue = " + queue);
}

Output results:

queue = [3]
queue = [3, 7]
queue = [3, 7, 5]
poll = 1 queue = [3, 7, 5]
poll = 3 queue = [5, 7, 8]

It can be seen from the results that the minimum value pops up each time.

4. Sort map by value

There are two schemes to sort keys according to the Value value in Map:

• Save key in queue
• Save map in the queue entry

4.1 save key in queue

Map<Integer, Integer> map = new HashMap<>();
// The value is stored in the map. It is no longer written here

// Create priority queues and define comparison rules
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
    public int compare(Integer a, Integer b) {
        return map.get(a) - map.get(b);  // Sort by Value in ascending order
    }
});

// Join the queue and sort
for (Integer key: map.keySet()) {
    queue.offer(key);  // When you join the queue, you sort
}

/*************************************************************************/
// When creating a priority queue, it can also be simplified as follows
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
    return map.get(a) - map.get(b);
});

4.2 save map in queue entry

Take < key, value > in the Map as a whole and use the Map Entry < > can be taken out. The difference from the above method is that Integer is changed into Map Entry < Integer, Integer >, others, I don't see them at the moment.

Map<Integer, Integer> map = new HashMap<>();
// The value is stored in the map. It is no longer written here

// Create priority queues and define comparison rules
PriorityQueue<Map.entry<Integer, Integer>> queue = new PriorityQueue<>((a, b) -> {
    return a.getValue() - b,getValue();
});

// Set<Map.entry<Integer, Integer>> set = map.entrySet();
// Join the queue and sort
for (Map.entry<Integer, Integer> entry: map.entrySet()) {
    queue.offer(entry);  // When you join the queue, you sort
}