《黑马程序员》— 索引优先队列

目录​​​​​​​

前言

实现步骤

代码实现


前言

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

实现步骤

步骤一: 存储数据时,给每一个数据元素关联一个整数,例如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; //把最小值赋值给当前结点
        }
    }
}

上一篇:公路村村通


下一篇:图 -邻接表广度优先遍历(C语言)