java算法之自定义最大索引优先队列

/** 
 * @desc: 自定义索引优先队列，可修改，删除索引对应的值 
 * @author: 毛会懂 
 * @create: 2021-01-06 17:20:00 
 **/ 
public class MyIndexPriorityQueue<T extends Comparable<T>> { 
    private T[] arr;//存储数组元素 
    private int[] pq;//存储元素的下标，符合堆结构 
    private int[] qp;//存储元素下标的堆的反序,pq数组中的值作为索引，pq数组的索引作为值j 
    private int size; 
 
    public MyIndexPriorityQueue(Integer size){ 
        arr = (T[])new Comparable[size]; 
        pq = new int[size + 1]; 
        qp = new int[size + 1]; 
        for (int i = 0; i < qp.length; i++) { 
            //默认情况下，qp逆序中不保存任何索引 
            qp[i] = -1; 
        } 
        this.size = 0; 
    } 
 
    //队列大小 
    public Integer getSize(){ 
        return size; 
    } 
 
    //是否为空 
    public Boolean isEmpty(){ 
        return size == 0; 
    } 
 
    //某一个位置是否有元素 
    public Boolean contains(int k){ 
        return qp[k] != -1; 
    } 
 
    //指定位置，添加元素 
    public void add(int i,T t){ 
        arr[i] = t; 
        size++; 
        //元素的下标需要符合堆结构 
        pq[size] = i; 
        qp[i] = size; 
        swim(size); 
    } 
 
    //删除最大元素 
    public T delMax(){ 
        if(size <= 0){ 
            return null; 
        } 
        T t = arr[pq[1]]; 
        change(1,size); 
        size--; 
        sink(1); 
        return t; 
    } 
 
    //修改某一个位置的元素 
    public void update(int k ,T t){ 
        if(!contains(k)){ 
            return; 
        } 
        //修改元素值 
        arr[k] = t; 
        //找到此元素在pq的下标 
        int index = qp[k]; 
        //上浮 
        swim(index); 
        //下沉 
        sink(index); 
    } 
 
    //删除某一个位置元素 
    public void delete(int k){ 
        if(!contains(k)){ 
            return; 
        } 
        //删除元素 
        arr[k] = null; 
        //交换位置 
        int index = qp[k]; 
        change(index,size); 
        //删除下标 
        qp[pq[size]] = -1; 
        pq[size] = -1; 
        size--; 
        //上浮 
        swim(index); 
        //下沉 
        sink(index); 
    } 
 
    //最小元素关联的索引 
    public int getMinIndex(){ 
        if(size >=1) { 
            return pq[1]; 
        } 
        return -1; 
    } 
 
 
    //上浮 
    private void swim(int k){ 
        while (k > 1){ 
            if(great(k,k/2)){ 
                change(k,k/2); 
            } 
            k = k /2; 
        } 
    } 
 
    //下沉 
    private void sink(int k){ 
        while (2 * k <= size){ 
            int max; 
            if(2 * k + 1 <= size) { 
                if (great(2 * k, 2 * k + 1)) { 
                    max = 2 * k; 
                } else { 
                    max = 2 * k + 1; 
                } 
            }else{ 
                max = 2 * k; 
            } 
            if(great(max,k)){ 
                change(max,k); 
            } 
            k = max; 
        } 
    } 
 
    private Boolean great(int i,int j){ 
        return arr[pq[i]].compareTo(arr[pq[j]]) > 0; 
    } 
 
    private void change(int i,int j){ 
        int temp = pq[i]; 
        pq[i] = pq[j]; 
        pq[j] = temp; 
         
        qp[pq[i]] = i; 
        qp[pq[j]] = j; 
    } 
}