1. Concept:
   Heap is also called priority queue. When entering the queue, it is the same as ordinary queue, but when leaving the queue, the elements with higher priority are given priority. When the priority is the same, it is carried out in the way of first in first out. The essence of heap is actually a binary tree, and this binary tree needs to meet the following three conditions:
   ①:
   Satisfy the condition of complete binary tree, that is, when a node has no child nodes or no right nodes, all nodes behind it can no longer have child nodes.
   ②:
   For any subtree in the whole tree, the value of the root node must be less than or greater than the value of the left and right child nodes, which is called small heap and large heap. And if you meet a small pile, you can't meet a large pile, and vice versa.
   Heap is usually stored by array. A priority queue is obtained by traversing a complete binary tree that meets the above conditions in sequence and storing the traversal results in the array.

2. Operation of heap:
   ① Downward adjustment: when the top element of the heap, that is, the first element of the team, changes, the rules of the whole heap are disrupted and need to be adjusted again.
   Premise: the left and right subtrees meet the rules of heap.
   Take a small pile as an example

public static void func(int size,int[] arr,int K){
        int parent = K;
        int child = parent*2+1;//Calculate the subscript of the child node through the subscript of the parent node
        while(child<size){//Child < size means that the current child node exists. Cannot be equal to because size is a number, calculated from 1, and child is a subscript, starting from 0
            if(child+1<size&&child+1<child){//child+1 represents the sibling node of child, and less than size means it also exists
                child = child+1;//Let the child time be the smallest of the two child nodes of the parent node
            }
            if(arr[parent]>arr[child]){//The value of parent node is greater than that of its child node. Because it is a small heap, it is necessary to exchange their values
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
            }else{//Represents that the heap rule is satisfied at this time, and the loop is ended directly
                break;
            }
            parent = child;//Continue to adjust downward from the position of the current child node until there are no child nodes. Adjustment completed
            child = parent*2+1;
        }
    }

Note: where size represents the valid heap element in the array, and K represents the subscript node from which to adjust

② We can build a heap according to the downward adjustment:

 public static void creat(int[] arr,int size){
        for(int i = (size-1-1)/2;i>=0;i--){
            func(size,arr,i);
        }

Note:
. size-1 represents the last node in the complete binary tree, that is, the last element in the array, (size-1-1) / 2 represents the position of the parent node of the last node, which is adjusted forward and downward from this position. When the tree top node is adjusted, the heap is built

③ Upward adjustment:
After entering the queue, another node is added at the end of the heap, and the rules of the heap are broken and need to be adjusted again
Take a small pile as an example

public static void func2(int[] arr,int K){
        int child = K;
        int parent = (child-1)/2;//The child node calculates the subscript of its parent node.
        while(child>=0){//When it is adjusted to the tree top, there is no need to adjust, because the tree top node has no parent node
            if(arr[parent]>arr[child]){//The small heap needs to satisfy that the parent node is smaller than the child node. At this time, it does not meet the need to exchange their values
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
            }else{
                break;
            }
            child = parent;//Let the child continue to adjust upward from the parent node until there is no parent node
            parent = (child-1)/2;
        }
    }

1. Implementing Priority Queues
   We can implement a priority queue set by adjusting up and down
   ① Enter the queue: it is equivalent to inserting an element at the end of the array, and then adjusting upward from the size-1 position

public  void offer(int x){
        arr[size] = x;//Tail x, that is, the end of the array, that is, the last node of the binary tree
        size++;
        func2(arr,size-1);
    }

② Out of queue: you need to get the value of the first element of the array and delete it. When deleting, you can assign the value of the tail element of the array to the head, then size –, and finally adjust it downward

public int poll(){//Out of queue
        //The element with subscript 0 is the team head element
        int oldvalue = arr[0];
        arr[0] = arr[size-1];//Assign the last element to the first element
        size--;//The last element is gone
        func(0,arr,size);//Then adjust downward from position 0
        return oldvalue;//Subscript element 0 is the team head element
    }

③ Take the first element of the queue: directly return the value of the first element of the array
④ Judge whether the queue is null: directly judge whether the size is 0.

1. Solve the TopK problem according to the heap:
   Through heap, we can easily solve the problem that the first K in a group of data is large or small. There are usually two solutions:
   ① : directly build a large / small heap on this group of data, and then cycle out of the queue K times
   ② : if you want to get the top k, create a small heap containing K elements. Every time you enter the queue in the subsequent queue, you will get out of the queue. In this way, the elements in the heap will be the top k elements, and vice versa.