优先队列

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

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

  1. 最大优先队列:可以获取并删除队列中最大的值
  2. 最小优先队列:可以获取并删除队列中最小的值

最大优先队列

我们之前学习过堆,而堆这种结构是可以方便的删除最大的值,所以接下来我们可以基于堆来实现最大优先队列

最大优先队列API设计

类名MaxPriorityQueue>
构造方法MaxPriorityQueue(int capacity):创建容量为capacity的MaxPriorityQueue对象
成员方法1.private boolean less(int i,int j):判断堆中索引i处的元素是否小于索引j处的元素 2.private void exch(int i,int j):交换堆中索引i和索引j的值 3.public T delMax():删除队列中最大的元素,并返回这个最大元素 4.publid void insert(T t):往队列中插入一个元素 5.private void swim(int k):使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置 6.private void sink(int k):使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置 7.public int size():获取队列中元素的个数 8.public boolean isEmpty():判断队列是否为空
成员变量1.private T[] imtes:用来存储元素的数组 2.private int N:记录堆中元素的个数

代码实现

MaxPriorityQueue

public class MaxPriorityQueue<T extends Comparable<T>> {

  /**
   * 用来存储元素的数组
   */
  private T[] items;
  /**
   * 记录堆中元素的个数
   */
  private int N;

  /**
   * 创建容量为capacity的MaxPriorityQueue对象
   */
  public MaxPriorityQueue(int capacity) {
    this.items = (T[]) new Comparable[capacity + 1];
    this.N = 0;
  }

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

  /**
   * 交换堆中索引i和索引j的值
   */
  private void exch(int i, int j) {
    T tem = items[i];
    items[i] = items[j];
    items[j] = tem;
  }

  /**
   * 删除队列中最大的元素,并返回这个最大的元素
   */
  public T delMax() {
    T max = items[1];
    exch(1, N);
    N--;
    sink(1);
    return max;
  }

  /**
   * 往队列中插入一个元素
   */
  public void insert(T t) {
    items[++N] = t;
    swim(N);
  }

  /**
   * 使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
   */
  private void swim(int k) {
    while (k > 1) {
      if (less(k / 2, k)) {
        exch(k / 2, k);
        k = k / 2;
      } else {
        break;
      }
    }
  }

  /**
   * 使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
   */
  private void sink(int k) {
    while (k * 2 <= N) {
      int max;
      if (2 * k + 1 <= N) {
        if (less(2 * k, 2 * k + 1)) {
          max = 2 * k + 1;
        } else {
          max = 2 * k;
        }
      } else {
        max = 2 * k;
      }
      if (less(k, max)) {
        exch(k, max);
        k = max;
      } else {
        break;
      }
    }
  }

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

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

MaxPriorityQueueTest

public static void main(String[] args) {
    //创建优先队列
    MaxPriorityQueue<String> priorityQueue = new MaxPriorityQueue<>(10);
    //往优先队列中存储元素
    priorityQueue.insert("A");
    priorityQueue.insert("B");
    priorityQueue.insert("C");
    priorityQueue.insert("D");
    priorityQueue.insert("E");
    priorityQueue.insert("F");
    priorityQueue.insert("G");
    //从队列中获取最大的元素
    while (!priorityQueue.isEmpty()) {
      String delMax = priorityQueue.delMax();
      System.out.print(delMax+" ");
    }
  }

最小优先队列

最小优先队列实现起来也比较简单,我们同样也可以基于堆来完成最小优先队列

我们前面学习堆的时候,堆中存放数据元素的数组都要满足如下特性

  1. 最大的元素放在数组的索引1处
  2. 每个节点的数据总是大于等于它的两个子节点的数据

其实我们之前实现的堆可以把它叫做最大堆,我们可以用相反的思想实现最小堆,让堆中存放数据元素的数组满足以下特性

  1. 最小的元素放在数组的索引1处
  2. 每个节点的数据总是小于等于它的两个子节点的数据

这样我们就能快速的访问到堆中最小的数据

最小优先队列API设计

类名MinPriorityQueue>
构造方法MinPriorityQueue(int capacity):创建容量为capacity的MinPriorityQueue对象
成员方法1.private boolean less(int i,int j):判断堆中索引i处的元素是否小于索引j处的元素 2.private void exch(int i,int j):交换堆中i索引和j索引处的值 3.public T delMin():删除队列中最小的元素,并返回这个最小元素 4.public void insert(T t):往队列中插入一个元素 5.private void swim(int k):使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置 6.private void sink(int k):使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置 7.public int size():获取队列中元素的个数 8.public boolean isEmpty():判断优先队列是否为空
成员变量1.private T[] items:用来存储元素的数组 2.private int N:记录堆中元素的个数

代码实现

MinPriorityQueue

public class MinPriorityQueue<T extends Comparable<T>> {

  /**
   * 用来存储元素的数组
   */
  private T[] items;
  /**
   * 记录堆中元素的个数
   */
  private int N;

  /**
   * 创建容量为capacity的MinPriorityQueue对象
   */
  public MinPriorityQueue(int capacity) {
    this.items = (T[]) new Comparable[capacity + 1];
    this.N = 0;
  }

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

  /**
   * 交换堆中i索引和j索引处的值
   */
  private void exch(int i, int j) {
    T temp = items[i];
    items[i] = items[j];
    items[j] = temp;
  }

  /**
   * 删除队列中最小的元素,并返回这个最小元素
   */
  public T delMin() {
    T min = items[1];
    exch(1, N);
    items[N] = null;
    N--;
    sink(1);
    return min;
  }

  /**
   * 往队列中插入一个元素
   */
  public void insert(T t) {
    items[++N] = t;
    swim(N);
  }

  /**
   * 使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
   */
  private void swim(int k) {
    //通过循环比较当前节点和它的父节点的大小
    while (k > 1) {
      if (less(k, k / 2)) {
        //如果比父节点还小,则交换
        exch(k, k / 2);
        k = k / 2;
      } else {
        break;
      }
    }
  }

  /**
   * 使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
   */
  private void sink(int k) {
    //通过循环比较当前节点与它的子节点的大小
    while (k * 2 <= N) {
      //如果存在右子节点
      int min;
      if (2 * k + 1 <= N) {
        //也存在左子节点,并且左子节点小于右子节点
        if (less(2 * k, 2 * k + 1)) {
          min = 2 * k;
        } else {
          min = 2 * k + 1;
        }
      }//如果不存在右子节点,直接min等于左子节点
      else {
        min = 2 * k;
      }
      //如果当前节点比min小,则不换
      if (less(k, min)) {
        break;
      }//如果小于,则换
      else {
        exch(k, min);
        k = min;
      }
    }
  }

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

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

MinPriorityQueueTest

public static void main(String[] args) {
    //创建最小优先队列对象
    MinPriorityQueue<String> minPriorityQueue = new MinPriorityQueue<>(10);
    //存入数据
    minPriorityQueue.insert("G");
    minPriorityQueue.insert("F");
    minPriorityQueue.insert("E");
    minPriorityQueue.insert("D");
    minPriorityQueue.insert("C");
    minPriorityQueue.insert("B");
    minPriorityQueue.insert("A");
    //通过循环得到最小优先队列的元素
    while (!minPriorityQueue.isEmpty()) {
      String delMin = minPriorityQueue.delMin();
      System.out.print(delMin + " ");
    }
  }

索引优先队列

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

索引优先队列实现思路

步骤1:

存储数据时,给每一个数据元素关联一个整数,例如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]即可

步骤2:

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

步骤3:

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

最直观的想法就是遍历pq数组,拿出每一个元素和0做比较,如果当前元素是0,那么调整该索引处的元素即可,但是效率很低

我们可以另外增加一个数组,int[] qp,用来存储pq的逆序,例如:

在pq数组中:pq[1]=6,那么在qp数组中,把6作为索引,1作为值,结果就是:qp[6]=1

索引优先队列API设计

类名IndexMinPriorityQueue>
构造方法IndexMinPriorityQueue(int capcacity):创建容量为capacity的IndexMinPriorityQueue对象
成员方法1.private boolean less(int i,int j):判断堆中索引i处的元素是否小于索引j处的元素 2.private void exch(int i,int j):交换堆中i索引和j索引处的值 3.public int delMin():删除队列中最小的元素,并返回该元素关联的索引 4.public void insert(int i,T t):往队列中插入一个元素,并关联索引i 5.private void swim(int k):使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置 6.private void sink(int k):使用下沉算法,使索引k处的元素能够在堆中处于一个正确的位置 7.public int size():获取队列中元素的个数 8.public boolean isEmpty():判断队列是否为空 9.public boolean contains(int k):判断k对应的元素是否存在 10.public void changeItem(int i,T t):把与索引i有关的元素修改为t 11.public int minIndex()::最小元素相关联的索引 12.public void delete(int i):删除索引i相关联的元素
成员变量1.private T[] items:用来存储元素的数组 2.private int[] pq:保存每个元素在items数组中的索引,pq数组需要堆有序 3.private int[] qp:保存qp的逆序,pq的值作为索引,pq的索引作为值 4.private int N:记录堆中元素的个数

代码实现

IndexMinPriorityQueue

public class IndexMinPriorityQueue<T extends Comparable<T>> {

  /**
   * 用来存储元素的数组
   */
  private T[] items;
  /**
   * 保存每个元素在items数组中的索引,pq数组需要堆有序
   */
  private int[] pq;
  /**
   * 保存qp的逆序,pq的值作为索引,pq的索引作为值
   */
  private int[] qp;
  /**
   * 记录堆中元素的个数
   */
  private int N;

  /**
   * 创建容量为capacity的IndexMinPriorityQueue对象
   */
  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;
    }
  }

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

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

  /**
   * 删除队列中最小的元素,并返回该元素关联的索引
   */
  public int delMin() {
    //获取最小元素关联的索引
    int minIndex = pq[1];
    //交换pq中索引1处和最大索引处的元素
    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 insert(int i, T t) {
//判断i是否已经被关联,如果已经被关联,则不让插入
    if (contains(i)) {
      return;
    } else {
      //元素个数+1
      N++;
      //把数据存储到items对应的i位置
      items[i] = t;
      //把i存储到pq中
      pq[N] = i;
      //通过qp来记录pq中的i
      qp[i] = N;
      //通过上浮算法来进行堆的调整
      swim(N);
    }
  }

  /**
   * 使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
   */
  private void swim(int k) {
    while (k > 1) {
      if (less(k, k / 2)) {
        exch(k, k / 2);
        k = k / 2;
      } else {
        break;
      }
    }
  }

  /**
   * 使用下沉算法,使索引k处的元素能在堆中处于一个正确的卫视
   */
  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;
      } else {
        exch(k, min);
        k = min;
      }
    }
  }

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

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

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

  /**
   * 把与索引i有关的元素修改为t
   */
  public void changeItem(int i, T t) {
    //修改items中位置为i的值为t
    items[i] = t;
    //找到i在pq中出现的位置
    int i1 = qp[i];
    //堆pq的调整
    swim(i1);
    sink(i1);
  }

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

  /**
   * 删除索引i相关联的元素
   */
  public void delete(int i) {
//找到i在pq中对应的索引
    int i1 = qp[i];
    //交换pq中索引i1的值与最后索引N的值
    exch(i1, N);
    //删除qp中原有的内容
    qp[pq[N]] = -1;
    //删除pq最后的内容
    pq[N] = -1;
    //删除items中的内容
    items[i1] = null;
    //元素数量-1
    N--;
    //先做上浮调整
    swim(i1);
    //再做下沉调整
    sink(i1);
  }
}

IndexMinPriorityQueueTest

public static void main(String[] args) {
    //创建索引最小优先队列对象
    IndexMinPriorityQueue<String> testIndex = new IndexMinPriorityQueue<>(10);
    //往队列中添加元素
    testIndex.insert(0, "A");
    testIndex.insert(1, "C");
    testIndex.insert(2, "F");
    testIndex.insert(3, "G");
    //测试修改
    testIndex.changeItem(2, "B");
    //测试删除
    while (!testIndex.isEmpty()) {
      int minIndex = testIndex.delMin();
      System.out.print(minIndex + " ");
    }
  }
Last modification:June 19th, 2021 at 07:58 pm