侧边栏壁纸
博主头像
coydone博主等级

记录学习,分享生活的个人站点

  • 累计撰写 306 篇文章
  • 累计创建 51 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

优先队列

coydone
2021-06-09 / 0 评论 / 0 点赞 / 292 阅读 / 3,077 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

概述

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

优先队列按照其作用不同,可以分为以下三种:

  • 最大优先队列:可以获取并删除队列中最大的值。

  • 最小优先队列:可以获取并删除队列中最小的值。

  • 索引优先队列:可以根据索引去操作队列中元素的值。

最大优先队列的实现就是堆的实现。最小优先队列可以通过改变推的判断条件改变。

索引优先队列

最大优先队列和最小优先队列,它们可以分别快速访问到队列中最大元素和最小元素,但是没有办法通过索引访问已存在于优先队列中的对象,并更新它们。

实现思路:

步骤一:存储数据时,给每一个数据元素关联一个整数,例如 insert(int k,T t) 可以看做k是t关联的整数,那么通过k这个值,快速获取到队列中t这个元素,此时有个k这个值需要具有唯一性。最直观的想法就是可以用一个 T[] items 数组来保存数据元素,在 insert(int k,T t) 完成插入时,可以把k看做是 items 数组的索引,把t元素放到items数组的索引k处,这样再根据k获取元素t时就很方便,直接就可以拿到 items[k]即可。

步骤二:步骤一完成后的结果,虽然给每个元素关联了一个整数,并且可以使用这个整数快速的获取到该元素,但是, items数组中的元素顺序是随机的,并不是堆有序的,所以可以增加一个数组int[]pq 来保存每个元素在items数组中的索引,pq数组需要堆有序,也就是说,pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]pq[3]对应的数据元素items[pq[2]]items[pq[3]]

步骤三:通过步骤二的分析,通过上浮和下沉做堆调整的时候,其实调整的是pq数组。如果需要对items中的元素进行修改,比如让items[0]=12,那么很显然,我们需要对pq中的数据做堆调整,而且是调整 pq[5]中元素的位置。但现在就会遇到一个问题,我们修改的是items数组中0索引处的值,如何才能快速的知道需要挑中pq[5]中元素的位置呢?最直观的想法就是遍历pq数组,拿出每一个元素和0做比较,如果当前元素是0,那么调整该索引处的元素即可, 但是效率很低。我们可以另外增加一个数组int[] qp用来存储pq的逆序。例如: 在pq数组中:pq[2]=7; 那么在qp数组中,把7作为索引,2作为值,结果是:qp[7]=2。

当有了pq数组后,如果我们修改items[0]=12,那么就可以先通过索引0,在qp数组中找到qp的索引:qp[0]=5,那么直接调整pq[5]即可。

public class IndexMinPriorityQueue {

    private Double[] items;
    private int[] pq;
    private int[] qp;
    private int n;

    public IndexMinPriorityQueue(int capacity) {
        items = new Double[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;
        }
    }

    //返回队列大小
    public int size() {
        return n;
    }

    //比较i和j处值的大小
    private boolean less(int i, int j) {
        return items[pq[i]] < items[pq[j]];
    }

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

    //交换i和j处的值
    private void exch(int i, int j) {
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

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

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

    //上浮算法,使索引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 (k * 2 <= n) {
            // 找出子结点中最小值的索引
            int minIndex = 2 * k;
            // 如果有右结点,并且右结点小于左节点
            if (k * 2 + 1 <= n && less(k * 2 + 1, k * 2)) {
                minIndex = 2 * k + 1;
            }
            // 如果当前节点小于子节点中的最小值,则结束循环
            if (less(k, minIndex)) {
                break;
            }
            // 当前节点大,交换
            exch(minIndex, k);
            ;
            k = minIndex;
        }
    }

    //往队列中插入一个元素,并关联索引
    public void insert(int i, double t) {
        // 判断一下当前索引是否存在元素
        if (contains(i)) {
            System.out.println("当前索引" + i + "已存在元素");
            return;
        }
        // 不存在,插入
        // 格式+1
        n++;
        // 把t存放到索引i处
        items[i] = t;
        // 使pq存放i这个索引
        pq[n] = i;
        // qp和pq是相反的,在qp的i处存放n这个数据
        qp[i] = n;
        // 元素存放完毕,上浮算法
        swim(n);
    }

    //删除队列中最小元素,并返回该元素关联的索引
    public Integer delMin() {
        // 最小元素的索引位置
        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;
        n--;
        // 下浮
        sink(1);
        return minIndex;
    }

    //把与索引i关联的元素修改为t
    public void changeItem(int i, double t) {
        items[i] = t;
        // 找到i在pq中的位置
        int k = qp[i];
        // 对pq[k]做下沉,让堆有序
        sink(k);
        // 对pq[k]做上浮,让堆有序
        swim(k);
    }

    //删除索引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);
    }
}
0

评论区