Skip to main content
 首页 » 编程设计

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

2022年07月18日24zengkefu
/** 
 * @desc: 自定义最小索引优先队列,可修改,删除索引对应的值 
 * @author: 毛会懂 
 * @create: 2021-01-06 17:20:00 
 **/ 
public class MyMinIndexPriorityQueue<T extends Comparable<T>> { 
    private T[] arr;//存储数组元素 
    private int[] pq;//存储元素的下标,符合堆结构 
    private int[] qp;//存储元素下标的堆的反序,pq数组中的值作为索引,pq数组的索引作为值j 
    private int size; 
 
    public MyMinIndexPriorityQueue(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 int delMin(){ 
        if(size <= 0){ 
            return -1; 
        } 
       // T t = arr[pq[1]]; 
        int t = pq[1]; 
        change(1,size); 
        size--; 
        sink(1); 
        return t; 
    } 
 
    //删除最小元素,返回删除的值 
    public T delMin2(){ 
        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(less(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 (less(2 * k, 2 * k + 1)) { 
                    max = 2 * k; 
                } else { 
                    max = 2 * k + 1; 
                } 
            }else{ 
                max = 2 * k; 
            } 
            if(less(max,k)){ 
                change(max,k); 
            } 
            k = max; 
        } 
    } 
 
    private Boolean less(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; 
    } 
}

测试代码:

//最小索引优先队列
public static void main(String[] args) {
MyMinIndexPriorityQueue queue = new MyMinIndexPriorityQueue(10);
queue.add(0,8);
queue.add(1,1);
queue.add(2,5);
queue.add(3,12);
queue.add(4,15);
queue.add(5,3);
queue.add(6,6);
queue.add(7,4);
queue.add(8,2);
queue.add(9,7);


System.out.println("最大的元素所在的索引:"+queue.getMinIndex());
System.out.println("修改元素");
for(int i = 0;i < 10;i++){
System.out.print(queue.delMin2() + ", ");
}
System.out.println("over");
}

本文参考链接:https://www.cnblogs.com/maohuidong/p/14278883.html