Heap (priority queue)

---

  Catalog

🥬 The nature of the heap

🥬 The classification of heaps

 🥬 Downward adjustment of the heap

🥬 Establishment of heap

🥬 Stack up adjustment

🥬 Common operation of heap

Queue entry

Outgoing queue

Get team leader elements

🥬TopK problem

🥬 Summary

---

🥬 The nature of the heap

The heap is logically a complete binary tree , The heap is physically stored in an array .

summary ： One Perfect binary tree With Sequence traversal Method is put into the array to store , The main use of this method is the representation of the heap .

also If Known father (parent) The subscript , be ：

Left the child (left) Subscript = 2 * parent + 1;

The right child (right) Subscript = 2 * parent + 2;

Known child （ There's no distinction between left and right ）(child) Subscript , be ：

Parents (parent) Subscript = (child - 1) / 2; 

🥬 The classification of heaps

A lot ： A complete binary tree whose root node is larger than the left and right child nodes （ The parent node is larger than its child node ）, It's called a lot of , Or a big pile , Or the largest heap .

Little heap ： A complete binary tree whose root node is smaller than the left and right child nodes is called Little heap （ The parent node is smaller than its child node ）, Or a small pile of roots , Or the smallest heap .

 🥬 Downward adjustment of the heap

Now there's an array , Logically, it is a complete binary tree , We pass from The root node At the beginning Downward adjustments The algorithm can adjust it into a small heap or a large heap . The downward adjustment algorithm has a premise ： The left and right subtrees must be a heap , To adjust .

Take a small pile as an example ：

1、 Let the left and right children compare , Minimum value .

2、 Compare the younger child node with the father node , If the child node < Father node , In exchange for , conversely , Don't swap .

3、 cycle , If the subscript of the child node is out of bounds , It means the end has come , ends .

Code example ：

 //parent:  The root node of each tree 
 //len:  The adjusted end position of each tree 

public void shiftDown(int parent,int len){
        int child=parent*2+1; // Because the heap is a complete binary tree , If there is no left child, there must be no right child , So at least there are left children , There are at least 1 A child 
        while(child<len){
            if(child+1<len && elem[child]<elem[child+1]){
                child++;// Compare the two child nodes and take the smaller value 
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

🥬 Establishment of heap

Give an array , Logically, this array can be regarded as a complete binary tree , But it's not a pile （ The left and right subtrees are not satisfied. They are all piles or small piles ）, Now let's go through the algorithm , Build it into a heap （ Piles or small piles ）. How do you do that ？ Here we start with the subtree of the penultimate non leaf node , Adjust the tree all the way to the root node , It can be adjusted into a pile . Here we will use what we just wrote Downward adjustments .

public void creatHeap(int[] arr){
        for(int i=0;i<arr.length;i++){
            elem[i]=arr[i];
            useSize++;
        }
        for(int parent=(useSize-1-1)/2;parent>=0;parent--){// Array index from 0 Start 
            shiftDown(parent,useSize);
        }
    }

  The space complexity of pile building is O（N）, Because the pile is a complete binary tree , A full binary tree is also a complete binary tree , We use a full binary tree （ In the worst case ） To prove .

🥬 Stack up adjustment

Now there is a heap , We need to insert data at the end of the heap , Then adjust it , Keep it in the heap structure , This is upward adjustment .

Take a large pile as an example ：

  Code example ：

public void shiftup(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

🥬 Common operation of heap

Queue entry

Add elements to the heap , Is to add to the last position , And then it's going up .

public boolean isFull(){
        return elem.length==useSize;
    }

public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);// Capacity expansion 
        }
        elem[useSize++]=val;
        shiftup(useSize-1);
    }

Outgoing queue

Delete the elements in the heap , Just exchange the top element with the last element , Then reduce the size of the entire array by one , Finally, adjust downward , The top element of the stack is deleted .

public boolean isEmpty(){
        return useSize==0;
    }

public int poll(){
        if(isEmpty()){
            throw new RuntimeException(" Priority queue is empty ");
        }
        int tmp=elem[0];
        elem[0]=elem[useSize-1];
        elem[useSize-1]=tmp;
        useSize--;
        shiftDown(0,useSize);
        return tmp;
    }

Get team leader elements

public int peek() {
        if (isEmpty()) {
            throw new RuntimeException(" Priority queue is empty ");
        }
        return elem[0];
    }

🥬TopK problem

Here you are. 6 Data , Seek before 3 Maximum data . At this time, how do we do with heaps ？

Their thinking ：

1、 If you ask before K The biggest element , To build a small root pile .
2、 If you ask before K The smallest element , To build a big pile .
3、 The first K Big elements . Build a small pile , The top of the heap element is the second K Big elements .
4、 The first K Small elements . Build a lot of , The top of the heap element is the second K Big elements .

for instance ： Seek before n Maximum data

  Code example ：

 public static int[] topK(int[] array,int k){
        // Create a size of K Small roots 
        PriorityQueue<Integer> minHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        // Traverse the elements in the array , Before the k Put elements in the queue 
        for(int i=0;i<array.length;i++){
            if(minHeap.size()<k){
                minHeap.offer(array[i]);
            }else{
                // from k+1 Elements start , Compare with the heap top elements respectively 
                int top=minHeap.peek();
                if(array[i]>top){
                    // Pop up before saving 
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        // Put the elements in the heap into the array 
        int[] tmp=new int[k];
        for(int i=0;i< tmp.length;i++){
            int top=minHeap.poll();
            tmp[i]=top;
        }
        return tmp;
    }

    public static void main(String[] args) {
        int[] array={12,8,23,6,35,22};
        int[] tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

  result ：

Array sorting

  Moreover, if you want to sort an array from small to large , Should we rely on big root pile or small root pile ？

----> Big root pile

  Code example ：

  public void heapSort(){
        int end=useSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);// Suppose we adjust it down to the big root heap 
            end--;
        }
    }

🥬 Summary

That's what we have today , If you have any questions, please leave a message in the comments area