## 1. Priority queue

1.1 concept

Queue is a first in, first out (FIFO) data structure. However, in some cases, the operation data may have priority. Generally, when leaving the queue, the elements with high priority may need to leave the queue first. In this scenario, using queue is obviously inappropriate. For example, when playing games on mobile phones, if there is a 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 introduction to common interfaces

1.2.1 characteristics of PriorityQueue

Two types of priority queues, PriorityQueue and PriorityBlockingQueue, are provided in the Java collection framework. PriorityQueue is a line

The process is unsafe. PriorityBlockingQueue is thread safe. This article mainly introduces PriorityQueue

Pay attention when using

1. When using, 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 compare the size, and cannot insert objects that cannot compare the size, otherwise they will be thrown

ClassCastException exception

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

5. The time complexity of inserting and deleting elements is

6. The bottom layer of PriorityQueue uses heap data structure. (Note: you can ignore what heap is here, which will be introduced later.)

7. PriorityQueue is a small heap by default -- that is, the smallest element is obtained every time

## 1.2.2 introduction to common interfaces of PriorityQueue

## constructor | ## Function introduction |

## PriorityQueue() | ## Create an empty priority queue with a default capacity of 11 |

## PriorityQueue(int | ## Create a priority queue with an initial capacity of initialCapacity. Note: |

## PriorityQueue(Collection<? | ## Create a priority queue with a collection |

## 1. Construction of priority queue

static void TestPriorityQueue(){ // Create an empty priority queue. The default capacity of the bottom layer is 11 PriorityQueue<Integer> q1 = new PriorityQueue<>(); // Create an empty priority queue with the underlying capacity of initialCapacity PriorityQueue<Integer> q2 = new PriorityQueue<>(100); ArrayList<Integer> list = new ArrayList<>(); list.add(4); list.add(3); list.add(2); list.add(1); // Use the ArrayList object to construct an object of priority queue // q3 already contains three elements PriorityQueue<Integer> q3 = new PriorityQueue<>(list); System.out.println(q3.size()); System.out.println(q3.peek()); }

Note: by default, the PriorityQueue queue is a small heap. If a large heap is required, the user needs to provide a comparator

// User defined Comparator: directly implement the Comparator interface, and then rewrite the compare method in the interface class IntCmp implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { return o2-o1; } } public class TestPriorityQueue { public static void main(String[] args) { PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp()); p.offer(4); p.offer(3); p.offer(2); p.offer(1); p.offer(5); System.out.println(p.peek()); } }

## Function name | ## Function introduction |

## boolean | ## Insert element E and return true after successful insertion. If the e object is empty, a NullPointerException exception is thrown |

## E peek() | ## Get the element with the highest priority. If the priority queue is empty, return null |

## E poll() | ## Remove the element with the highest priority and return it. If the priority queue is empty, return null |

## int size() | ## Get the number of valid elements |

## void | ## empty |

## boolean | ## Check whether the priority queue is empty, and return true if it is empty |

static void TestPriorityQueue2(){ int[] arr = {4,1,9,2,8,0,7,3,6,5}; // In general, when creating priority queue objects, if you know the number of elements, it is recommended to directly give the underlying capacity // Otherwise, little capacity expansion is required during insertion // Capacity expansion mechanism: open up more space and copy elements, so the efficiency will be relatively low PriorityQueue<Integer> q = new PriorityQueue<>(arr.length); for (int e: arr) { q.offer(e); } S ystem.out.println(q.size()); // Number of effective elements in the print priority queue System.out.println(q.peek()); // Get the element with the highest priority // Delete the sum of the two elements from the priority queue and get the element with the highest priority again q.poll(); q.poll(); System.out.println(q.size()); // Number of effective elements in the print priority queue System.out.println(q.peek()); // Get the element with the highest priority q.offer(0); System.out.println(q.peek()); // Get the element with the highest priority // Delete the valid elements in the priority queue and check whether they are empty q.clear(); if(q.isEmpty()){ System.out.println("Priority queue is empty!!!"); } e lse{ System.out.println("Priority queue is not empty"); } }

Note: the following is the capacity expansion method of PriorityQueue in JDK 1.8

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

## Description of priority queue expansion:

If the capacity is less than 64, it is expanded by twice the oldCapacity

If the capacity is greater than or equal to 64, it is expanded by 1.5 times the oldCapacity

If the capacity exceeds MAX_ARRAY_SIZE, according to MAX_ARRAY_SIZE for capacity expansion

1.3 application of priority queue (key)

top-k problem: the largest or smallest top k data. For example, the world's top 500 companies

class Solution { public int[] smallestK(int[] arr, int k) { // Parameter detection if(null == arr || k <= 0) return new int[0]; PriorityQueue<Integer> q = new PriorityQueue<>(arr.length); // Put the elements in the array into the heap in turn for(int i = 0; i < arr.length; ++i){ q.offer(arr[i]); } / / Put the top of the priority queue k Put elements into the array int[] ret = new int[k]; for(int i = 0; i < k; ++i){ ret[i] = q.poll(); } r eturn ret; } }

## 2. Simulation implementation of priority queue

The underlying PriorityQueue in JDK1.8 uses the data structure of the heap, and the heap actually adjusts some elements on the basis of a complete binary tree.

2.1 concept of reactor

If there is a key set K = {k0, k1, k2,..., kn-1}, store all its elements in a complete binary tree

In a one-dimensional array, and satisfy: ki < = k2i+1 and Ki < = k2i+2 (KI > = k2i+1 and Ki > = k2i+2) I = 0, 1, 2..., it is called a small heap (or large

Heap). The heap with the largest root node is called the maximum heap or the large root heap, and the heap with the smallest root node is called the minimum heap or the small root heap.

Nature of heap:

The value of a node in the heap is always not greater than or less than the value of its parent node;

Heap is always a complete binary tree.

2.2 storage mode of heap

According to the concept of heap, heap is a complete binary tree, so the rules of sequence can be stored in a sequential manner,

Note: for incomplete binary trees, it is not suitable to use sequential storage, because in order to restore the binary tree, empty sections must be stored in the space

Point, which will lead to low space utilization.

After storing the elements in the array, the tree can be restored according to the property 5 of the binary tree chapter. Assuming i is the subscript of the node in the array, there are:

If i is 0, the node represented by i is the root node; otherwise, the parent node of node i is (i - 1)/2

If 2 * i + 1 is less than the number of nodes, the left child subscript of node i is 2 * i + 1, otherwise there is no left child

If 2 * i + 2 is less than the number of nodes, the subscript of the right child of node i is 2 * i + 2, otherwise there is no right child

Example

1.The following keyword sequence is heap:() A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60 D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 F: 50,100,70,65,60,32 2.Known small root heap is 8,15,10,21,34,16,12，After deleting keyword 8, the heap needs to be rebuilt. In this process, the number of comparisons between keywords is() A: 1 B: 2 C: 3 D: 4 3.A group of record sorting codes are(5 11 7 2 3 17),Then the initial heap established by using the heap sorting method is() A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5) D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5) 4.Minimum heap[0,3,2,5,7,4,6,8],After deleting the heap top element 0, the result is() A: [3，2，5，7，4，6，8] B: [2，3，5，7，4，6，8] C: [2，3，4，5，7，8，6] D: [2，3，4，5，6，7，8] [Reference answer] 1.A 2.C 3.C 4.C

2.3 heap creation

2.3.1 stack down adjustment

For the data in the set {27,15,19,18,28,34,65,49,25,37}, what if we create it into a heap?

After careful observation of the above figure, it is found that the left and right subtrees of the root node have fully satisfied the nature of the heap, so you only need to adjust the root node downward.

Downward process (taking small heap as an example):

1. Let the parent mark the node that needs to be adjusted, and the child mark the left child of the parent (Note: if the parent has children, it must have left children first)

2. If the left child of the parent exists, that is: child < size, carry out the following operations until the left child of the parent does not exist

Whether the right child of the parent exists. Find the youngest child of the left and right children and let the child mark

Compare the parent with the younger child if:

The parent is smaller than the younger child, and the adjustment is over

Otherwise: exchange the parent with the child of the younger child. After the exchange is completed, the large element in the parent moves downward, which may lead to the child

The tree does not satisfy the nature of the pair, so it needs to continue to adjust downward, that is, parent = child; child = parent*2+1; Then continue 2

public void shiftDown(int[] array, int parent) { // Child marks the left child of the parent first, because the parent may be right, left or not right int child = 2 * parent + 1; int size = array.length; while (child < size) { // If the right child exists, find the smaller one of the left and right children and mark it with child if(child+1 < size && array[child+1] < array[child]){ child += 1; } / / If the parents are younger than their youngest child, it means that the structure has met the characteristics of heap if (array[parent] <= array[child]) { break; }else{ // Swap parents for younger children int t = array[parent]; array[parent] = array[child]; array[child] = t; // Moving down the large elements in the parent may cause the subtree to not meet the nature of the heap, so it needs to continue to adjust downward parent = child; child = parent * 2 + 1; } } }

Note: when adjusting a binary tree with a parent as the root, you must satisfy that the left and right subtrees of the parent are already heaped before you can adjust downward.

Time complexity analysis:

The worst case is the case shown in the figure. The number of comparisons from root to leaf is the height of the complete binary tree, that is, the time complexity is Olog2n

2.3.2 heap creation

Then how to adjust the ordinary sequence {1,5,3,8,7,6}, that is, the left and right subtrees of the root node do not meet the characteristics of the heap

public static void createHeap(int[] array) { // Find the penultimate non leaf node, starting from the position of the node and going forward to the root node. If you encounter a node, apply downward adjustment int root = ((array.length-2)>>1); for (; root >= 0; root--) { shiftDown(array, root); } }

2.3.3 time complexity of reactor construction

Because the heap is a complete binary tree, and the full binary tree is also a complete binary tree, the full binary tree is used here for simplification (the time complexity is originally seen as

Approximate value, more nodes do not affect the final result):

Therefore, the time complexity of reactor building is O(N)

## 2.4 heap insertion and deletion

2.4.1 heap insertion

There are two steps to insert the heap:

1. Put the elements into the bottom space first (Note: when the space is insufficient, it needs to be expanded)

2. Adjust the last newly inserted node upward until it meets the nature of the heap

public void shiftUp(int child) { // Find child's parents int parent = (child - 1) / 2; while (child > 0) { // If the parents are older than the children, and the parents meet the nature of the heap, the adjustment is over if (array[parent] > array[child]) { break; } e lse{ // Exchange parent and child nodes int t = array[parent]; array[parent] = array[child]; array[child] = t; // When small elements move down, it may be that the value subtree does not meet the nature of pairs, so it needs to continue to increase upward child = parent; parent = (child - 1) / 1; } } }

## 2.4.2 deletion of heap

Note: deleting the heap must delete the top element of the heap. The details are as follows:

1. Exchange the top element of the heap with the last element in the heap

2. Reduce the number of valid data in the heap by one

3. Adjust the top element downward

## 2.5 using heap simulation to realize priority queue

public class MyPriorityQueue { // Demo function, no longer consider the code of the expansion part private int[] array = new int[100]; private int size = 0; public void offer(int e) { array[size++] = e; shiftUp(size - 1); } public int poll() { int oldValue = array[0]; array[0] = array[--size]; shiftDown(0); return oldValue; } public int peek() { return array[0]; } }