堆排序与加强堆代码 用于记忆

堆排序

public static void getBigHeap(int[] arr){
        for(int i=0;i
            heapInsert(arr,i);
        }
    }

    
    public static int[] getRandomArr(int maxLength,int maxValue){
        int len=(int)(Math.random()*maxLength)+2;
        int[] arr=new int[len];
        for(int i=0;i
            arr[i]=(int)(Math.random()*maxValue);
        }
        return arr;
    }

    
    public static void heapInsert(int[] arr ,int index){
        while(arr[(index-1)/2]
            swap(arr,(index-1)/2,index);
            index=(index-1)/2;
        }

    }

    
    public static void heapIfy(int[] arr,int index,int heapSize){
        int left= index*2+1;
        while(left
            int largest=left+1arr[left]?left+1:left;
            largest=arr[largest]>arr[index]?largest:index;

            if(index==largest){
                break;
            }
            swap(arr,largest,index);
            index=largest;
            left=index*2+1;
        }
    }


    public static void swap(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
   

加强堆

public class HeapGreater {

    //存放堆的数组
    private ArrayList heap;

    //反向索引表
    private HashMap indexMap;

    //堆大小
    private int heapSize;

    //比较器
    private Comparator comp;


    //初始化这个加强堆
    public HeapGreater(Comparator c){
        this.comp=c;
        indexMap=new HashMap<>();
        heapSize=0;
        heap=new ArrayList<>();
    }

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

    public int size(){
        return this.heapSize;
    }

    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);
        heapInsert(heapSize++);
    }

    public T pop(){
        T ans=heap.get(0);
        swap(0,heapSize-1);  //将头移动到尾部
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);    //从头开始重新调整堆的位置
        return ans;
    }

    //移除堆上的任意一个节点
    public void remove(T obj){
        T replace=heap.get(heapSize-1);
        int index=indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if(obj!=replace){
            heap.set(index,replace);
            indexMap.put(replace,index);
            resign(replace);
        }

    }

    
    public void resign(T obj){
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    
    public List returnAllElements(){
        ArrayList ts = new ArrayList<>();
        for(T t: heap){
            ts.add(t);
        }
        return ts;
    }

    
    public 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;

        }
    }

    
    public void heapify(int index){
        int left=index*2+1;
        while(left
            int best=left+1
                break;
            }
            swap(best,index);
            index=best;
            left=index*2+1;
        }
    }

    
    public void swap(int i,int j){
        T o1=heap.get(i);
        T o2=heap.get(j);
        heap.set(i,o2);
        heap.set(j,o1);
        indexMap.put(o2,i);
        indexMap.put(o1,j);

    }

}

两种堆中最重要的是3个方法
heapify，heapInsert ，swap