目录​​​​​​​

前言

实现步骤

代码实现

---

前言

上一个博客实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一个缺点，就是没有办法通过索引访问已存在于优先队列中的对象，并更新。 为了实现这个目的，在优先队列的基础上，学习一种新的数据结构， 索引优先队列 。接下来我们以最小索引优先队列举列。 原理：以空间换时间，利用 两个辅助数组来维护优先队列。

实现步骤

步骤一： 存储数据时，给每一个数据元素关联一个整数，例如insert(int k,T t)。例如 可以用一个 T[] items 数组来保存数据元素，在 insert(int k,T t) 完成插入时，可以把 k 看做是 items 数组的索引， 把t元素放到items数组的索引k处 。 步骤二： 步骤一完成后的结果，虽然我们给每个元素关联了一个整数，但是items数组中的元素顺序是随机的，并不是堆有序的，需要增加一个数组 int[]pq, 来保存每个元素在items 数组中的索引， pq数组需要堆有序 。例如 pq[1] 对应的数据元素 items[pq[1]] 要小于等 于 pq[2] 和 pq[3] 对应的数据元 items[pq[2]] 和 items[pq[3]] 。 步骤三： 为了方便快速调整items中的元素， 构建pq数组的逆序 int[] qp，例如： 在 pq 数组中：pq[1]=6; 那么在 qp 数组中，把 6 作为索引， 1 作为值，结果是： qp[6]=1。 当有了pq数组后，如果我们修改items[0]="H"，那么就可以先通过索引0，在qp数组中找到qp的索引：qp[0]=9, 那么直接调整pq[9] 即可。

代码实现

代码API

package tree2;

public class IndexMinPriorityQueue <T extends Comparable<T>>{
    private T[] items;
    private int[] pq;
    private int[] qp;
    private int N;

    public IndexMinPriorityQueue(int capacity){
        this.items = (T[]) new Comparable[capacity+1];
        this.pq = new int[capacity+1];
        this.qp = new int[capacity+1];
        this.N = 0;

        //默认情况下，队列中没有存储任何书籍，让qp的元素都为-1
        for(int i=0; i<qp.length; i++){
            qp[i] =- 1;
        }
    }

    //获取队列元素的个数
    public int size(){
        return N;
    }

    //判断队列是否为空
    public boolean inEmpty(){
        return N==0;
    }

    //判断堆中元素大小
    private boolean less(int i, int j){
        return items[pq[i]].compareTo(items[pq[j]])<0;
    }

    //交换堆中元素值
        private void exch(int i, int j){
            int tmp = pq[i];
            pq[i] = pq[j];
            pq[j] = tmp;

            //更新qp中的数据
            qp[pq[i]] = i;
            qp[pq[j]] = j;
        }

    //判断k对应的元素是否存在
    public boolean contains(int k){
        return qp[k] != -1;
    }

    //最小元素关联的索引
    public int minIndex(){
        return pq[1];
    }

    //往队列中插入一个元素
    public void insert(int i, T t){
        // 判断i是否已经被关联，如果已经被关联，不让插入
        if (contains(i)){
            return;
        }
        N++;
        //把数据存储到items对应的i位置处
        items[i] = t;
        // 把i存储到pq中
        pq[N] = i;
        // 用qp来记录pq的i
        qp[i] = N;

        //保持堆有序
        swim(N);
    }

    // 删除队列中最小的元素，并返回该元素关联的索引
    public int delMin(){
        int minIndex =  pq[1];
        // 交换pq
        exch(1,N);
        // 删除qp中对应的内容
        qp[pq[N]] = -1;
        // 删除pq最大索引处的内容
        pq[N] = -1;
        // 删除items中对应的内容
        items[minIndex] = null;
        // 元素个数-1
        N--;
        // 下沉调整
        sink(1);

        return minIndex;
    }

    // 删除索引i关联的元素
    public void delete(int i){
        //找出i在pq中的索引
        int k = pq[i];
        exch(k,N);
        qp[pq[N]] = -1;
        pq[N] = -1;
        items[k] = null;
        N--;
        // 因为元素k是在数组中的中间，所以需要先下沉再上浮，或者先上浮再下沉
        sink(k);
        swim(k);
    }

    // 修改索引i关联的元素为t
    public void changeItem(int i, T t){
        items[i] = t;
        int k = qp[i];
        sink(k);
        swim(k);
    }

    // 上浮算法
    private void swim(int k){
        while(k>1){
            if(less(k,k/2)){
                exch(k,k/2); //这里面已经更新了pq[]和qp[]
            }
            k = k/2;
        }
    }

    //下沉算法
    private void sink(int k){
        while(2*k<=N){
            int min;
            if (2*k+1<=N){
                if(less(2*k,2*k+1)){
                    min = 2*k;
                }else{
                    min = 2*k + 1;
                }
            }else{
                min = 2*k;
            }

            //比较当前结点和较小值
            if (less(k,min)){
                break;
            }
            exch(k,min);
            k = min; //把最小值赋值给当前结点
        }
    }
}