Heap classical problem

Array build heap structure （ Take the big root pile for example ）

package com.zzf.algorithm;

/** * @author zzf * @date 2022-01-28 */
public class Heap {
    

    public static class MyMaxHeap{
    
        private int[] heap;
        private final int limit;
        private int heapSize;

        public MyMaxHeap(int limit){
    
            heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }

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

        public boolean isFull(){
    
            return heapSize == limit;
        }

        public void push(int value){
    
            if(heapSize == limit){
    
                throw new RuntimeException(" Pile up ");
            }
            heap[heapSize] = value;
            heapInsert(heap,heapSize++);
        }

        public int pop(){
    
            int ans = heap[0];
            swap(heap,0,--heapSize);// The last position and the starting position are exchanged 
            heapfy(heap,0,heapSize);// Continuously sinking the large root pile for adjustment 
            return ans;
        }

        // Heap sort 
        public void heapSort(int[] heap){
    
            if(heap == null || heap.length < 2){
    
                return;
            }

            // Build the heap structure 
            // The first one is , Build one by one , From the top down O(N*logN)
            /*for (int i = 0;i < heap.length-1;i++){ heapInsert(heap,i); }*/
            // The second kind , Directly in the case of data , From the bottom to the top O(N)
            for (int i = heap.length-1; i >= 0; i--) {
    
                heapfy(heap,i,heap.length);
            }
            // Constantly swap and build the heap structure , Large values are put behind 
            int heapSize = heap.length;
            swap(heap,0,--heapSize);
            while (heapSize > 0){
    
                heapfy(heap,0,heapSize);
                swap(heap,0,--heapSize);
            }
        }

        private void heapfy(int[] heap, int index, int heapSize) {
    
            int left = index * 2 + 1;
            // With a left child 
            while (left < heapSize){
    
                // Keep the subscript of the older child 
                int largest = left+1 < heapSize && heap[left+1] > heap[left] ? left + 1 : left;
                // Compare the current position with the larger position 
                largest = heap[largest] > heap[index] ? largest : index;
                if(largest == index){
     // The current position is the largest , No adjustment 
                    break;
                }
                swap(heap,largest,index);// Exchange adjustment 
                index = largest;
                left = index * 2 + 1;
            }
        }

        // Newly added value , Put it in index Location , Then move up and adjust to the large root heap 
        private void heapInsert(int[] heap, int index) {
    

            // Keep adjusting up , until index by 0 Or the parent node 
            while (heap[index] > heap[(index - 1) / 2]){
    
                swap(heap,index,(index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void swap(int[] heap, int a, int b) {
    
            int tmp = heap[a];
            heap[a] = heap[b];
            heap[b] = tmp;
        }
    }
}

Conditional sorting using heap

Ideas ： Build a small root heap , Make sure there is at most k Number （ Note the array size and k Size ）, The first 0-k-1 Put in the number of positions , Pop up a minimum value in turn , Put it in 0 Location , Then join in k The number of positions , Then the cycle . Until there is no number to add , And if there are still numbers in the heap , Just pop it up and put it in the corresponding position , In this way, it is ensured that the moving distance before and after each number sorting does not exceed k

package com.zzf.algorithm;

import java.util.PriorityQueue;

/** * @author zzf * @date 2022-01-29 */
public class SortArrayDistanceLessK {
    

    // Sort an array , Let the number move no more than... Before and after sorting k
    public static void sortedArrDistanceLessK(int[] arr, int k){
    
        if(k == 0)
        {
    
            return;
        }
        // Heap 
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        int index = 0;
        // The former k Add the number to the small root pile 
        for(;index <= Math.min(arr.length - 1, k - 1);index++){
    
            heap.add(arr[index]);
        }
        int i = 0;
        for(;index < arr.length;i++,index++){
    
            // Pop up a number , Put it in i Location 
            arr[i] = heap.poll();
            heap.add(arr[index]);// Add next number 
        }

        // There are no numbers to add , Just pop up the rest of the heap and put it in i Location 
        while (!heap.isEmpty()){
    
            arr[i++]  = heap.poll();
        }
    }
}

Heap optimization , For non base types , The contents of the elements in the heap change dynamically , Take the small root pile for example

package com.zzf.algorithm;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/** * @author zzf * @date 2022-01-29 */
public class HeapGreater<T> {
    
    private ArrayList<T> heap;
    private HashMap<T,Integer> indexMap;
    private int heapSize;
    private Comparator<? super T> comp;

    public HeapGreater(Comparator<T> c){
    
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }

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

    public int size(){
    
        return heapSize;
    }

    // Determine whether the heap contains a value 
    public boolean contains(T obj){
    
        return indexMap.containsKey(obj);
    }

    public T peek(){
    
        return heap.get(0);
    }

    public void push(T obj){
    
        heap.add(obj);
        indexMap.put(obj,heapSize);// Record the position of the value in the heap 
        heapInsert(heapSize++);
    }

    public T pop(){
    
        T ans = heap.get(0);
        swap(0,heapSize - 1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0); // Adjust the heap 
        return ans;
    }

    // Remove an element from the heap 
    public void remove(T obj){
    
        // Save the last node value first 
        T replace = heap.get(heapSize - 1);
        //map Delete this node in 
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        //heap Remove the last node 
        heap.remove(--heapSize);
        if(obj != replace){
    
            // It is equivalent to that the last node is exchanged with the node to be removed 
            heap.set(index,replace);
            indexMap.put(replace,index);
            // Adjust the heap 
            resign(replace);
        }
    }

    // Adjustment operations to be done after content update 
    public void resign(T obj){
    
        int index = indexMap.get(obj);
        heapInsert(index);
        heapify(index);
    }

    private void heapify(int index) {
    
        int left = index * 2 + 1;
        while (left < heapSize){
    
            int best = left + 1 < heapSize &&
                    comp.compare(heap.get(left + 1),heap.get(left)) < 0 ? (left + 1) : left;
            best = comp.compare(heap.get(index),heap.get(best)) < 0 ? best : index;
            if(best == index){
    
                break;
            }
            swap(best,index);
            index = best;
            left = index * 2 + 1;
        }
    }

    private void heapInsert(int index) {
    
        while(comp.compare(heap.get(index),heap.get((index - 1) / 2)) < 0){
    
            swap(index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int i, int j) {
    
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        // Modify the value of the corresponding position 
        heap.set(i,o2);
        heap.set(j,o1);
        // to update map Information 
        indexMap.put(o2,i);
        indexMap.put(o1,j);
    }
}