1, Heap and related operations
 Heap structure is a complete binary tree structure implemented by array
size refers to the number of nodes
I position, left child 2i+1, right child 2i+2, parent node (i1)/2 rounded down  In a complete binary tree, if the maximum value of each subtree is at the top, it is a large root heap
 In a complete binary tree, if the minimum value of each subtree is at the top, it is a small root heap
 heapInsert and heapify operations of heap structure
 (1) Insert operation heapInsert
Insert the tail and constantly compare O(logN) with the parent node
//A number is now in the index position and continues to move upward public static void heapInsert(int[] arr,int index){ while(arr[index] > arr[(index  1) / 2]){ //The number of index positions > its parent node or has reached the head swap(arr,index,(index  1) / 2); //exchange index = (index  1) / 2; //The value of index is transformed to the original parent node } }

(2) Large root heap maximum operation
1. First return the maximum value of the large root heap (i.e. the root heapsize)
2. Put the last node at the root, compare it with the left and right children once, and keep sinking until the left and right children are smaller than it, or there are no children 
(3) Can I move heapify down
O(logN)
//Can a number move down when it is in the index position public static void heapify(int[] arr,int index,int heapSize){ int left = index * 2 + 1; //Left child subscript while(left < heapSize){ //When there are children below, if the left child is < size, there must be a right child < size //Which of the two children is the most valuable? Give the subscript to large int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; //Between the father and the older child, who is worth more, give the subscript to bigger largest = arr[largest] > arr[index] ? largest : index; if(largest == index){ //If the maximum value is index compared with children, it will jump out break; } swap(arr,largest,index); //Otherwise, exchange the values of index and largest index = largest; //index moves down to the position at the maximum value left = index * 2 + 1; //Update left and continue the cycle } }
 (4) Change the value of the i th node
Large root pile:
1. If the value of position I becomes smaller = > the heapify operation is performed down from position i
2. If the value of position I becomes larger = > the heapInsert operation is performed upward at position i
 Increase and decrease of reactor structure
 The priority queue structure is the heap structure
(heap ordering is often less important than heap structure)
PriorityQueue<Integer>heap = new PriorityQueue<>(); //Small root pile
2, Heap sort*
 Time complexity: O(NlogN)
 Space director: O(1)
 Large root pile:
1. Add the numbers in the sequence one by one and form a large root pile side by side.
2. Swap the maximum number of positions with the first element and return the maximum number of positions
3. Repeat the above process and return continuously to get the descending sequence
package com.godzuo.java; import java.util.Arrays; public class HeapSort { public static void heapSort(int[] arr){ if(arr == null  arr.length < 2) return; // for(int i = 0;i < arr.length;i++){ //O(N) // heapInsert(arr,i); // Build large root heap O(logN) // } for(int i = arr.length  1;i >= 0;i){ //O(N), the time complexity does not change, but the speed becomes faster, because it is sorted as O(NlogN). If you just become a heap, you should choose this method. heapify(arr,i,arr.length); } int heapSize = arr.length; swap(arr, 0, heapsize); //The number at position 0 is exchanged with the number at the last position on the heap, and the size of the heap after exchange while (heapsize > 0) { //O(N) heapify(arr, 0, heapsize); //The number at position 0 goes down and readjusts to large root heap O(logN) swap(arr, 0, heapsize); //Continue exchange,  O(1) } } } //Build large root pile public static void heapInsert(int[] arr,int i){ while (arr[i]>arr[(i1)/2]){ swap(arr,i,(i1)/2); i = (i1)/2; } } public static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } //Modify large root heap public static void heapify(int[] arr,int index,int heapSize){ int left = index*2+1; while (left < heapSize){ int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left+1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index){ break; } swap(arr,largest,index); index = largest; left = index*2+1; } } public static void main(String[] args) { int[] arr = {1,3,2,6,5,9}; heapSort(arr); System.out.println(Arrays.toString(arr)); } }
 improvement:
Instead of adjusting one after another, all of them will be added to the heapify from right to left.
3, Heap sorting problem expansion
[title]
An almost ordered array is known, which means that if the array is arranged in order, each element can move no more than k, and K is relatively small relative to the array. Please select an appropriate sorting algorithm to sort this data.
[analysis]
Time complexity: O (nlock) can be approximately equal to O(N)
public class SortArrayDistanceLessK(int[] arr,int k){ //Default small root heap PriorityQueue<Integer> heap = new PriorityQueue<>(); int index = 0; for(;index <= Math.min(arr.length,k);index++){ heap.add(arr[index]); // The first k numbers are arranged in a small root pile } int i = 0; for(;index < arr.length;i++,index++){ heap.add(arr[index]); //Add a value arr[i] = heap.poll(); //Play a value } while(!heap.isEmpty()){ arr[i++] = heap.poll; //Pop up the rest } }
4, Heap structure
//Java default small root heap PriorityQueue<Integer> heap = new PriorityQueue<>(); heap.add(8); heap.add(4); heap.add(9); heap.add(10); heap.add(3); while(!heap.isEmpty()) System.out.println(heap.poll());

Capacity expansion
Expansion times: logN
Cost per expansion: O(N)
Total cost of capacity expansion: O(NlogN)
Average capacity expansion cost: O(NlogN)/N=O(logN) 
Heap structure of the system
1. add and poll pop up
It is convenient, but it does not support the formed heap. After manual value change and other operations, it can be readjusted to heap at a very small cost
2. Handwritten heap can be implemented efficiently
5, Comparator
C + + overloaded comparison operator = = Java comparator
package com.godzuo.java; import java.util.Arrays; import java.util.Comparator; public class Comparator { public static class Student { public String name; public int id; public int age; public Student(String name, int id, int age) { this.name = name; this.id = id; this.age = age; } } public static class IdAscendingComparator implements Comparator<Student> { //Sort in ascending order by Id //!!! below!!! //When a negative number is returned, the first parameter comes first //When returning a positive number, the second parameter comes first //It doesn't matter who is in front when returning 0 @Override public int compare(Student o1, Student o2) { return o1.id  o2.id; //if(o1.id < o2.id) // return 1; //if(o1.id > o2.id) // return 1; //return 0; } } public static class IdDescendingComparator implements Comparator<Student> { //ID descending order @Override public int compare(Student o1, Student o2) { return o2.id  o1.id; } } public static class AgeAscendingComparator implements Comparator<Student> { //Ascending order of age @Override public int compare(Student o1, Student o2) { return o1.age  o2.age; } } public static class AgeDescendingComparator implements Comparator<Student> { //Age descending comparator @Override public int compare(Student o1, Student o2) { return o2.age  o1.age; } } public static void printStudents(Student[] students) { for (Student student : students) { System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age); } System.out.println("==========================="); } public static void main(String[] args) { Student student1 = new Student("A", 2, 20); Student student2 = new Student("B", 3, 21); Student student3 = new Student("C", 1, 22); Student[] students = new Student[] { student3, student2, student1 }; printStudents(students); Arrays.sort(students, new IdAscendingComparator()); //System comparison size: array, policy printStudents(students); Arrays.sort(students, new IdDescendingComparator()); printStudents(students); Arrays.sort(students, new AgeAscendingComparator()); printStudents(students); Arrays.sort(students, new AgeDescendingComparator()); printStudents(students); //Built in heap structure PriorityQueue<Student> heap = new PriorityQueue<>(new AgeAscendingComparator()); heap.add(student1); heap.add(student2); heap.add(student3); while (!heap.isEmpty()){ Student student = heap.poll(); System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age); } } }
 Comparators can also be used in ordered structures
1. If you don't transfer things, it is organized by small root heap by default
public static void main(String[] args){ PriorityQueue<Integer> heap = new PriorityQueue<>(); heap.add(8); heap.add(4); heap.add(9); heap.add(10); heap.add(3); while(!heap.isEmpty()) System.out.println(heap.poll()); }
2. Pass to comparator, sort by large root heap
public class HeapTest{ public static class AComp implements Comparator<Integer> { //!!! below!!! //Returns a negative number, with the first parameter listed above //Returns a positive number, with the second parameter listed above //When you return 0, it doesn't matter who is in front @Override public int compare(Integer arg0, Integer arg1) { return arg1  arg2; } } public static void main(String[] args){ PriorityQueue<Integer> heap = new PriorityQueue<>(new AComp()); //Incoming comparator heap.add(8); heap.add(4); heap.add(9); heap.add(10); heap.add(3); while(!heap.isEmpty()) System.out.println(heap.poll()); } }
 The essence of comparator is to overload comparison operators
 The comparator can be well applied to the sorting of special standards
 The comparator can be well applied to the structure sorted according to special standards (such as heap)
6, Cardinality sort
Sorting not based on comparison is based on data conditions, and has less application scope than sorting based on comparison. (eg: count sort, cardinality sort)
Put them into the bucket in order according to the number, ten, hundred, thousand, ten thousand, etc., and then pour them out in order.
The highest priority is the last.
Base sorting: there should be base (base digits = = number of buckets)
import java.util.Arrays; public class RadixSort{ //only for nonegative value public static void radixSort(int[] arr){ if(arr == null  arr.length < 2){ return; } radixSort(arr,0,arr.length  1,maxbits(arr)); } public static int maxbits(int[] arr){ int max = Integer.MIN_VALUE; for(int i = 0;i < arr.length;i++){ max = Math.max(max,arr[i]); //Maximum found } int res = 0; while(max != 0){ res++; max /= 10; } return res; //How many decimal digits does the maximum have } //arr[begin...end] sort public static void radixSort(int[] arr,int L,int R,int digit){ //The number of decimal digit s in this batch is R to L final int radix = 10; //Based on 10 bits int i = 0,j = 0; //How many auxiliary spaces are there int[] bucket = new int[R  L + 1]; for(int d = 1;d <= digit;d++){ //The number of bits in and out of the bucket is the number of times, that is, the traversal of the number of bits //10 spaces //count word frequency array = > prefix and //count[0] is the number of numbers whose current bit (d bit) is 0 //count[1] is the number of current bits (d bits) that are (0 and 1) //count[2] is the number of numbers whose current bits (d bits) are (0, 1 and 2) //count[0] is the number of current bits (d bits) that are (0~i) int[] count = new int[radix]; //count[0...9] for(i = L;i <= R;i++){ j = getDigit(arr[i],d); //d=1 takes out one digit number, d=2 takes out one hundred digit number count[j]++; //Calculate the number of each number at each location } for (i = 1;i < radix;i++){ count[i] = count[i] + count[i  1]; //Calculate prefix and } for(i = R;i >= L;i){ //Array traversal from right to left j = getDigit(arr[i],d); //Take out the number of d bits bucket[count[j]  1] = arr[i]; //Put it in the last bit of the slice where the auxiliary array is located count[j]; //Prefix of j and  1 } //Count all the buckets and put them into the bucket for(i = L,j = 0;i <= R;i++,j++){ arr[i] = bucket[j]; //Import the numbers in the bucket into the arr } } //Cycle, and the number at the next position will come out of the barrel and into the barrel } public static int getDigit(int x,int d){ return ((x / ((int) Math.pow(10,d  1))) % 10); } }
All numbers are traversed from right to left and put into the last position of the piece, which can ensure the first in and first out of the barrel; And from the right, you can count the number less than this number to determine your position.