Priority queue (heap)

The sequential storage of binary trees

storage

Use array to save binary tree structure , Method is to put the binary tree into the array by sequence traversal .
Generally, it is only suitable for representing complete binary tree , Because incomplete binary trees will waste space .
The main use of this method is the representation of the heap .

Subscript relation

1. Known parents (parent) The subscript , be ：
   Left the child (left) Subscript = 2 * parent + 1;
   The right child (right) Subscript = 2 * parent + 2;
2. Known child （ There's no distinction between left and right ）(child) Subscript , be ：
   Parents (parent) Subscript = (child - 1) / 2;

Pile up

Concept

1. The heap is logically a complete binary tree
2. The heap is physically stored in an array
3. Satisfy that the value of any node is greater than the value of the node in its subtree , It's called a lot of , Or a big pile , Or the largest heap . conversely , It's a small pile , Or a small pile of roots , Or the smallest heap .

Basic operation

Building the heap

 public void creatBigHeap(int[] array) {
    
    	for(int i=0;i<array.length;i++) {
    
    		elem[i]=array[i];
    		 usedSize++;
    	}
    	for(int parent=(usedSize-1-1)/2;parent>=0;parent--) {
    
    		// adjustment 
    		shiftDown(parent,usedSize);
    	}
    }
  //parent: The root node of each tree  len: The end position of each tree adjustment 
    public void shiftDown(int parent,int len) {
    
    	int child=2*parent+1;
    	while(child < len) {
    
    		if( child+1 < len &&elem[child] < elem[child+1]) {
    
    			child++;// Ensure the current subscript of the maximum value of the left and right children 
    		}
    		if(elem[child] > elem[parent]) {
    
    			int tmp=elem[child];
    			elem[child]=elem[parent];
    			elem[parent]=tmp;
    			parent=child;
    			child=2*parent+1;
    		}else {
    
    			break;
    		}
    	}
    }

The team

  // Queue entry （ Take a large pile as an example ）
    public void offer(int val) {
    
    	if(isFull()) {
    
    		// Capacity expansion 
    		elem=Arrays.copyOf(elem, elem.length *2);
    		
    	}
    	elem[usedSize]=val;
    	usedSize++;
    	// Notice what's coming in here usedSize-1
    	shiftUp(usedSize-1);
    }
    public boolean isFull() {
    
    	return usedSize==elem.length;
    }

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

Out of the team

 // Out of the team 
    public int poll() {
    
    	if(isEmpty()) {
    
    		throw new RuntimeException(" Priority queue is empty ");
    	}
    	 int tmp=elem[0];
		 elem[0]=elem[usedSize-1];
		 elem[usedSize-1]=tmp;
		 usedSize--;
    	 shiftDown(0,usedSize);
    	 // Return the element to be dequeued 
    	 return tmp;
    }
    public boolean isEmpty() {
    
    	return usedSize==0;
    }
  public void shiftDown(int parent,int len) {
    
    	int child=2*parent+1;
    	while(child < len) {
    
    		if( child+1 < len &&elem[child] < elem[child+1]) {
    
    			child++;// Ensure the current subscript of the maximum value of the left and right children 
    		}
    		if(elem[child] > elem[parent]) {
    
    			int tmp=elem[child];
    			elem[child]=elem[parent];
    			elem[parent]=tmp;
    			parent=child;
    			child=2*parent+1;
    		}else {
    
    			break;
    		}
    	}
    }

Get team leader elements

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

top-K problem

Heap sort

 public void heapSort() {
    
    	int end=usedSize-1;
    	while(end>0) {
    
    		 int tmp=elem[0];
    		 elem[0]=elem[end];
    		 elem[end]=tmp;
    		 shiftDown(0,end);
    	     end--;
    	}
    }