数据结构与算法之索引优先队列

冷不防 2023-10-03 18:00 39阅读 0赞

在前面实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一 个缺点，就是没有办法通过索引访问已存在于优先队列中的对象，并更新它们。为了实现这个目的，在优先队列的 基础上，学习一种新的数据结构，索引优先队列。接下来我们以**最小索引优先队列举列**。

#### 最小索引优先队列实现思路 ####

**步骤一**： 存储数据时，给每一个元素关联一个索引，我们用一个T\[ \] items数组来保存数据元素，在insert(T t，int k)插入时，k就是 items数组的索引，元素 t 放到items数组的索引k处，这样我们根据k获取元素 t 时就很方便了， T t = items\[k\]即可。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16][]

**步骤二：** 步骤一完成后，虽然我们给每个元素关联了一个索引，并且可以使用索引快速的获取到元素，但是， items数组中的元素顺序是随机的，并不是堆有序的。所以，为了完成这个需求，我们需要增加一个数组int\[ \] index，来保存每个元素在items数组中的索引，index数组需要堆有序，如index\[1\]对应的数据元素items\[index\[1\]\]要小于等于index\[2\]和index\[3\]对应的数据元素items\[index\[2\]\]和items\[index\[3\]\]

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

int\[ \] index数组存放items数组元素对应的索引（index数组中的数据对应的元素满足堆有序），如下所示

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_17_color_FFFFFF_t_70_g_se_x_16][]

**步骤三：** 通过步骤二的分析，我们可以发现，其实我们通过上浮和下沉做堆调整的时候，其实调整的是index\[ \]数组。如果需要对items\[ \]中的元素进行修改，比如让items\[0\]=“H”，那么很显然，我们需要对index\[ \]中的数据做堆调整，而且是调整 index\[ \]中9索引处数据的位置。但现在就会遇到一个问题，我们修改的是items数组中0索引处的值，如何才能快速的知道需要调整index\[ \]中哪个索引处的数据？

最直观的想法就是遍历index\[ \]数组，拿出每一个数据和0做比较，如果当前数据是0，那么调整该索引处的数据即可， 但是效率很低。

我们有更好的解决方法：另外增加一个数组，int\[ \] indexReverse,用来存储index\[ \]的逆数据。

例如： 在index数组中，index\[1\]=6，那么在indexReverse数组中，把6作为索引，1作为值，即indexReverse\[6\]=1。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

int\[ \] index数组存放items数组元素对应的索引（index数组中的数据对应的元素满足堆有序）

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_17_color_FFFFFF_t_70_g_se_x_16][]

int\[ \] indexReverse数组存放index数组的索引值（不包括0）

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

当有了index数组后，如果我们修改items\[0\]="H"，那么就可以先通过索引0，在indexReverse数组中找到index数组的索引：indexReverse\[0\]=9, 接下来调整index\[9\]即可。

#### **最小索引优先队列API设计** ####

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

#### 索引优先队列代码实现 ####

/**
     * @author: xuzhilei
     * @create: 2021-12-20
     * @description: 基于最小优先队列的索引优先队列
     **/
    public class IndexMinPriorityQueue<T extends Comparable<T>> {
        /**
         * 存储元素的数组
         */
        private final T[] items;
        /**
         * 存储元素在数组items中的索引值，需满足items[index[i]]小于等于items[index[2i]]、
         * items[index[i]]小于等于items[index[2i+1]]
         */
        private final int[] index;
        /**
         * 存储index数组的逆序，即index的值为indexReverse的索引，
         * index的索引为indexReverse的值
         */
        private final int[] indexReverse;
        /**
         * 记录队列中元素个数
         */
        private int number;
    
        /**
         * 构造方法
         */
        public IndexMinPriorityQueue(int capacity) {
            this.items = (T[]) new Comparable[capacity + 1];
            this.index = new int[capacity + 1];
            this.indexReverse = new int[capacity + 1];
            this.number = 0;
            //默认情况下，indexReverse数组不保存index的任何索引
            Arrays.fill(indexReverse, -1);
        }
    
        /**
         * 判断队列是否为空
         *
         * @return boolean
         */
        public boolean isEmpty() {
            return number == 0;
        }
    
        /**
         * 获取队列中元素个数
         *
         * @return int
         */
        public int size() {
            return number;
        }
    
        /**
         * 判断index数组中i索引处对应的items数组元素是否小于j索引处对应的items数组元素
         *
         * @param i index数组中的索引
         * @param j index数组中的索引
         * @return boolean
         */
        public boolean less(int i, int j) {
            return items[index[i]].compareTo(items[index[j]]) < 0;
        }
    
        /**
         * 交换index数组中i索引与j索引处的值
         *
         * @param i index数组中的索引
         * @param j index数组中的索引
         */
        public void exchange(int i, int j) {
            //交换index数组中的值
            int temp = index[i];
            index[i] = index[j];
            index[j] = temp;
            //更新indexReverse数组
            indexReverse[index[i]] = i;
            indexReverse[index[j]] = j;
        }
    
        /**
         * 判断数组items中索引k处对应的元素是否存在
         * （数组items索引与数组indexReverse索引保持一致）
         *
         * @param k items数组索引(即indexReverse数组索引)
         * @return boolean
         */
        public boolean isExist(int k) {
            //默认情况下，indexRevers数组中的值都为-1，如果数组items索引k处插入了元素，
            // 则indexRevers数组索引k处的值不为-1
            return indexReverse[k] != -1;
        }
    
        /**
         * items中最小元素的索引
         *
         * @return items数组索引
         */
        public int indexOfMin() {
            //index数组索引1处的值即为items数组中最小元素的索引
            return index[1];
        }
    
        /**
         * 往队列中插入元素t并关联索引i
         *
         * @param t 待插入元素
         * @param i items数组索引（即indexReverse[]索引）
         */
        public void insert(T t, int i) {
            //如果索引i处已经存在元素，则不允许插入
            if (isExist(i)) {
                return;
            }
            //items索引i处储存t
            items[i] = t;
            //队列元素个数+1
            number++;
            //使用index存储i
            index[number] = i;
            //使用indexRevers来记录i和number
            indexReverse[i] = number;
            //使用上浮算法调整数组index对应的元素items[index[number]]
            floutUp(number);
        }
    
        /**
         * 删除队列中最小的元素，并返回该元素
         *
         * @return items[]中的最小元素
         */
        public T deleteMin() {
            //获取最小元素关联的索引
            int indexOfMin = index[1];
            //记录最小的元素
            T min = items[indexOfMin];
            //交换index中索引1处和最大索引处的值
            exchange(1, number);
            //删除indexReverse数组中的记录
            indexReverse[index[number]] = -1;
            //删除index最大索引处的值
            index[number] = -1;
            //删除items中对应的元素
            items[indexOfMin] = null;
            //元素个数-1
            number--;
            //对index数组1索引处的值做下沉调整
            sink(1);
            //返回最小的元素关联的索引
            return min;
        }
    
        /**
         * 删除索引i关联的元素
         *
         * @param i items数组索引(即indexReverse数组索引)
         */
        public void delete(int i) {
            //找到索引i在index[]中对应的索引
            int k = indexReverse[i];
            //交换index[]中索引k与索引number处的值
            exchange(k, number);
            //删除indexReverse数组中的记录
            indexReverse[index[number]] = -1;
            //删除index[]最大索引处的值
            index[number] = -1;
            //删除items中对应的元素
            items[i] = null;
            //元素个数-1
            number--;
            //对index数组k索引处的值做堆调整
            floutUp(k);
            sink(k);
        }
    
        /**
         * 把索引i关联的元素修改为t
         *
         * @param i items数组索引（即indexReverse[]索引）
         * @param t 新值
         */
        public void update(int i, T t) {
            //找到索引i在index[]中对应的索引
            int k = indexReverse[i];
            //修改i索引处的值为t
            items[i] = t;
            //对index数组k索引处的值做堆调整
            floutUp(k);
            sink(k);
        }
    
    
        /**
         * 使用上浮算法，使索引k处的值对应的元素在堆中处于合适的位置
         *
         * @param k index数组中索引
         */
        private void floutUp(int k) {
            while (k > 1) {
                if (less(k, k / 2)) {
                    exchange(k, k / 2);
                }
                k = k / 2;
            }
        }
    
        /**
         * 使用下沉算法，使索引k处的值对应的元素在堆中处于合适的位置
         *
         * @param k index数组中索引
         */
        private void sink(int k) {
            while (2 * k <= number) {
                //记录子结点中的较小值
                int min;
                //如果存在右子结点
                if (2 * k + 1 <= number) {
                    if (less(2 * k, 2 * k + 1)) {
                        min = 2 * k;
                    } else {
                        min = 2 * k + 1;
                    }
                } else {
                    min = 2 * k;
                }
                //比较当前结点与最小结点的大小
                if (less(k, min)) {
                    break;
                }
                //交换索引k与索引min处的值
                exchange(k, min);
                //变换k
                k = min;
    
            }
        }
    
    
        //测试
        public static void main(String[] args) {
            String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
            IndexMinPriorityQueue<String> queue = new IndexMinPriorityQueue<>(20);
            //向队列放数据
            for (int i = 0; i < arr.length; i++) {
                queue.insert(arr[i], i);
            }
            //获取队列元素个数
            int size = queue.size();
            System.out.println(size);
    
            //获取最小元素对应的索引
            //int indexOfMin = queue.indexOfMin();
            //System.out.println(indexOfMin);
    
            删除最小元素并返回该元素
            //System.out.println(queue.deleteMin());
    
            //测试修改
            queue.update(0, "z");
            //从小到大删除队列中的元素
            while (!queue.isEmpty()) {
                int indexOfMin = queue.indexOfMin();
                String min = queue.deleteMin();
                System.out.println(indexOfMin + "=" + min);
            }
        }
    
    }

测试结果：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

以上是个人随手敲的demo，如有不正确的地方，可以在下方留言指正，谢谢。与各位CSDN的伙伴们共勉，每天记录一点点，每天进步一点点

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/bbd8a085e63b432db29be6b81805a02b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/20d73ce970f845f0bd2d62a523efbe22.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/58bfa8173bf24c7c8e3438f34a8d2b5d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/45e1c51d1b254483bf714e48682908c8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/7d7465041ee0421380dbb4e04d53e17e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/9c4dd7f8cc7844c993017b3c716a08e8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/98a0fcedcdf544d8b7eddc278b4b738c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16