• 队列的原理和实现代码

    1 优先队列概述

    ● 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，我们可能需要找出队列中的最大最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我们需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。
    ● 普通队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候我们就可以使用一种特殊的队列来完成这个需求，优先队列
    在这里插入图片描述

    2 最大优先队列

    2.1 概述

    ● 由于堆这种结构可以方便的删除最大的值，所以我们使用基于堆这种数据结构来实现最大优先队列

    2.2 代码实现

    public class MaxPriorityQueue<T extends Comparable<T>> {
    // 定义一个数组，存储数据
    private T[] items;
    // 计算数组中的个数
    private int N;

    // 构造方法，初始化数组和N
    public MaxPriorityQueue(int capacity) {
        items = (T[]) new Comparable[capacity + 1];
        N = 0;
    }

    // 返回数组元素个数
    public int size() {
        return N;
    }

    // 判断数组是否为空
    public boolean isEmpty() {
        return N == 0;
    }

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

    // 交换元素
    public void exch(int i, int j) {
        T tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }

    // 向堆中插入元素
    public void insert(T t) {
        items[++N] = t;
        swim(N);

    }

    // 删除最大元素
    public T delMax() {
        T max = items[1];
        exch(1, N);
        N--;
        sink(1);
        return max;
    }

    // 使用上浮算法，将插入进去的元素调整到合适的位置
    private void swim(int k) {
        // 判断是否到根节点，如果到根节点则结束循环
        while (k > 1) {
            // 判断父节点是否小于该节点，如果小于该节点则进行交换
            if (less(k / 2, k)) {
                exch(k / 2, k);
            }
            k = k / 2;
        }
    }

    private void sink(int k) {
        // 判断是否到最后一层，如果到最后一层则结束循环
        while (2 * k <= N) {
            // 定义一个临时变量，储存两个子节点中最大的索引值
            int max = 2 * k;
            // 判断该节点是否有右节点
            if (2 * k + 1 <= N) {
                // 如果有右节点，则判断左节点大还是右节点大
                if (less(2 * k, 2 * k + 1)) {
                    // 如果右节点大，则将右节点的索引值赋值给max
                    max = 2 * k + 1;
                }
            }

            // 判断子节点和该节点那个节点较大
            if (!less(k,max)){
                // 如果该节点较大，则结束循环
                break;
            }
            // 如果该节点较小，则继续循环比较
            exch(k,max);
            k = max;
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88

    3 最小优先队列

    ● 把最小的元素放在数组的索引1处
    ● 每个节点的数据总是小于等于它的两个子节点的数据
    在这里插入图片描述

    ● 代码实现

    public class MinPriorityQueue {
    public class MaxPriorityQueue<T extends Comparable<T>> {
        // 定义一个数组，存储数据
        private T[] items;
        // 计算数组中的个数
        private int N;

        // 构造方法，初始化数组和N
        public MaxPriorityQueue(int capacity) {
            items = (T[]) new Comparable[capacity + 1];
            N = 0;
        }

        // 返回数组元素个数
        public int size() {
            return N;
        }

        // 判断数组是否为空
        public boolean isEmpty() {
            return N == 0;
        }

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

        // 交换元素
        public void exch(int i, int j) {
            T tmp = items[i];
            items[i] = items[j];
            items[j] = tmp;
        }

        // 向堆中插入元素
        public void insert(T t) {
            items[++N] = t;
            swim(N);

        }

        // 删除最小元素
        public T delMin() {
            T max = items[1];
            exch(1, N);
            N--;
            sink(1);
            return max;
        }

        // 使用上浮算法，将插入进去的元素调整到合适的位置
        private void swim(int k) {
            // 判断是否到根节点，如果到根节点则结束循环
            while (k > 1) {
                // 判断该节点是否小于父节点，如果小于父节点则进行交换
                if (less(k, k/2)) {
                    exch(k, k/2);
                }
                k = k / 2;
            }
        }

        private void sink(int k) {
            // 判断是否到最后一层，如果到最后一层则结束循环
            while (2 * k <= N) {
                // 定义一个临时变量，储存两个子节点中最小的索引值
                int min = 2 * k;
                // 判断该节点是否有右节点
                if (2 * k + 1 <= N) {
                    // 如果有右节点，则判断左节点小还是右节点小
                    if (less(2 * k+1, 2 * k )) {
                        // 如果右节点小，则将右节点的索引值赋值给min
                        min = 2 * k + 1;
                    }
                }

                // 判断子节点和该节点那个节点较小
                if (less(k,min)){
                    // 如果该节点较小，则结束循环
                    break;
                }
                // 如果该节点较大，则继续循环比较
                exch(min,k);
                k = min;
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    4 索引优先队列

    4.1 概述

    ● 最小和最大优先队列可以快速的获取到最大和最小的值，但是无法通过索引访问优先队列中的对象
    ● 而索引优先队列则可以通过缩影快速的访问到队列中的值

    4.2 索引优先队列实现思路

    ● 步骤一
    ○ 创建一个item数组来保存数据元素，我们可以通过insert(int k,T t)将索引存储在数组中，可以通过k值获取队列中的数据元素
    在这里插入图片描述

    ● 步骤二
    ○ 当我们把数据元素根据索引存放到数组中时，此时数据元素在数组中是无序的，并不是堆排序
    ○ 此时，我们需要增加一个数组pq，来保存items数组中的索引值，pq数组需要根据items元素值进行堆排序
    在这里插入图片描述

    ● 步骤三
    ○ 当我们进行上浮和下沉调整的时，实际上是调整pq数组，当我们需要对items数组中的元素进行修改时，pq数组需要重新进行排序。
    ○ 当我们修改items[0]处的值时，我们需要去pq数组中寻找0在pq数组的那个位置，然后对其进行上浮或下沉调整，我们可以通过遍历pq数组找出0在pq数组的那个位置然后对其进行修改，可这样效率较低
    ○ 我们可以创建一个新的数组qp来保存pq数组的逆序，这样当我们需要修改items中的元素时，我们可以先通过qp数组获取到pq数组中的位置，然后对其进行上浮或下沉的调整，这样就减少了遍历pq数组的过程
    在这里插入图片描述

    4.3 代码实现

    import javax.swing.plaf.nimbus.AbstractRegionPainter;

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

    // 构造方法，初始化元素
    public IndexMinPriorityQueue(int capacity) {
        items = (T[]) new Comparable[capacity + 1];
        pq = new int[capacity + 1];
        qp = new int[capacity + 1];
        N = 0;
        for (int i = 0; i < qp.length; i++) {
            qp[i] = -1;
        }
    }

    // 判断堆pq中i处索引的值是否小于j处索引的值
    private boolean less(int i, int j) {
        // 先通过pq找出items中的索引值，然后在找出items中的元素进行比较
        return items[pq[i]].compareTo(items[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;

    }

    // 删除队列中最小的值
    public int delMin() {
        // 找到items中最小元素的索引
        int minIndex = pq[1];
        // 交换pq中索引1处的值和N处的值
        exch(1, N);
        // 删除qp中索引pq[N]处的值
        qp[pq[N]] = -1;
        // 删除pq中索引索引N处的值
        pq[N] = -1;
        // 删除items中的最小元素
        items[minIndex] = null;
        // 元素数量-1；
        N--;
        // 对pq[1]做下沉调整，让堆有序
        sink(1);
        return minIndex;
    }

    // 向队列插入元素
    public void insert(int i, T t) {
        // 判断要插入的索引处是否有值，如果有则不能插入
        if (contains(i)) {
            throw new RuntimeException("该索引已经存在");
        }
        // 个数+1
        N++;
        // 把元素存放到items中
        items[i] = t;
        // 将索引i存放到pq数组中
        pq[N] = i;
        // 将N存放在qp数组的i处
        qp[i] = N;
        // 使用上浮算法，让pq有序
        swim(N);
    }

    // 上浮算法
    private void swim(int k) {
        while (k > 1) {
            // 比较当前节点和父节点，如果当前节点比父节点小，则交换位置
            if (less(k, k / 2)) {
                exch(k, k / 2);
            }
            k = k / 2;
        }

    }

    // 下沉算法
    private void sink(int k) {
        // 如果当前节点没有子节点了，就结束循环
        while (2 * k <= N) {
            // 找出子节点中的较小值
            int min = 2 * k;
            if (2 * k + 1 <= N && less(2 * k + 1, 2 * k)) {
                min = 2 * k + 1;
            }
            // 如果当前节点比子节点较小值还小，则继续下沉，否则结束循环
            if (less(k, min)) {
                break;
            }
            exch(k, min);
            k = min;
        }

    }

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

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

    // 判断k对应的元素是否为空
    public boolean contains(int k) {
        // 在初始化时，qp中的值为-1，如果插入了元素，那么qp中的值就不是-1
        return qp[k] != -1;
    }

    // 把索引i关联的元素改为t
    public void changeItem(int i, T t) {
        // 修改items数组中的元素索引处的值为t
        items[i] = t;
        //通过qp找到i在pq中的位置
        int k = qp[i];
        // 对堆进行调整使其有序
        sink(k);
        swim(k);
    }

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

    // 删除索引i所关联的元素
    public void delete(int i) {
        // 找出i在索引pq中的索引
        int k = qp[i];
        // 把pq中索引k处的值和索引N处的值交换
        exch(k, N);
        // 删除qp中索引pq[N]处的值
        qp[pq[N]] = -1;
        // 删除pq中索引N处的值
        pq[N] = -1;
        // 删除items中索引i处的元素值
        items[i] = null;
        //元素-1
        N--;
        // 对堆进行调整，使其有序
        sink(k);
        swim(k);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
  • 相关阅读:
    pytorch widedeep文档
    java计算机毕业设计建筑劳务监管平台MyBatis+系统+LW文档+源码+调试部署
    M. My University Is Better Than Yours(思维)
    一文快速回顾 Servlet、Filter、Listener
    Maven开发配置教程
    东郊到家app小程序公众号软件开发预约同城服务系统成品源码部署
    C++ 容器 详解
    nginx转发规则
    混入组件 (mixin)
    云计算基础知识
  • 原文地址：https://blog.csdn.net/weixin_48626604/article/details/126366692