【笔记】队列之索引优先队列

前言

队列之索引（最小）优先队列的Java版API实现

源代码

package com;

/**
 * 索引（最小）优先队列
 */
public class IndexMinPriorityQueue<T extends Comparable<T>> {

    private T[] data;
    // 保存每个元素在data中的索引，pq数组需要堆有序
    private int[] pq;
    // 保存pq的逆序（pq的值作为索引，pq的索引作为值）
    private int[] qp;
    private int indexMinPriorityQueueLength;

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

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

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

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

    // 判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return data[pq[i]].compareTo(data[pq[j]]) < 0;
    }

    // 交换堆中i索引处和j索引处的值
    private void exch(int i, int j) {
        // 交换pq中的数据
        int tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
        // 更新qp中的数据
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    // 判断索引k处的元素是否存在
    private boolean contains(int k) {
        return qp[k]!=-1;
    }

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

    // 往队列中插入一个元素，并关联索引i
    public void insert(int i, T t) {
        // 判断i是否已经被关联，如果已经被关联，则不允许插入
        if (contains(i)) {
            return;
        }
        // 元素个数+1
        indexMinPriorityQueueLength++;
        // 把数据存储到data
        data[i] = t;
        // 把i存储到pq中
        pq[indexMinPriorityQueueLength] = i;
        // 通过qp记录pq中的i
        qp[i] = indexMinPriorityQueueLength;
        // 上浮调整
        swim(indexMinPriorityQueueLength);
    }

    // 删除队列中最小的元素，并返回该元素关联的索引
    public int delMin() {
        // 获取最小元素关联的索引
        int minIndex = pq[1];
        // 交换pq中索引1处和索引最大处的元素
        exch(1, indexMinPriorityQueueLength);
        // 删除qp中对应的内容
        qp[pq[indexMinPriorityQueueLength]] = -1;
        // 删除pq中最大索引处的内容
        pq[indexMinPriorityQueueLength] = -1;
        // 删除data中对应的内容
        data[minIndex] = null;
        // 元素自减
        indexMinPriorityQueueLength--;
        // 下沉调整
        sink(1);
        return minIndex;
    }

    // 删除索引i处的元素
    public void delete(int i) {
        // 找到i在pq中的索引
        int k = qp[i];

        // 交换索引k处和最大索引处的值
        exch(k, indexMinPriorityQueueLength);
        // 删除qp中的内容
        qp[pq[indexMinPriorityQueueLength]] = -1;
        // 删除pq中的内容
        pq[indexMinPriorityQueueLength] = -1;
        // 删除data中的内容
        data[indexMinPriorityQueueLength] = null;
        // 元素的数量自减
        indexMinPriorityQueueLength--;
        // 堆的调整
        sink(k);
        swim(k);
    }

    // 修改索引i处的索引值为t
    public void changeItem(int i, T t) {
        // 修改data中索引i初的元素为t
        data[i] = t;
        // 找到i在pq中出现的位置
        int k = qp[i];
        // 堆调整
        sink(k);
        swim(k);
    }

    // 使用上浮算法，使索引k处的元素有序
    private void swim(int k) {
        while (k>1) {
            if (less(k, k/2)) {
                exch(k, k/2);
            }
            k = k/2;
        }
    }

    // 使用下沉算法，使索引k处的元素有序
    private void sink(int k) {
        while (2*k<=indexMinPriorityQueueLength) {
            // 找到子结点中的较小值
            int min;
            if (2*k+1<=indexMinPriorityQueueLength) {
                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;
        }
    }

}

完成

参考文献

哔哩哔哩——黑马程序员