优先队列

• 首先解释一下什么是队列？
  
  • 简单地理解的话优先队列其实就是一个FIFO（Fast In Fast Out）。
• 什么是优先队列？
  
  • 简单的理解就是在队列的基础上，每一个元素增加一个优先级，这样就会存在Last In 的队列元素Fast Out了。每次从队列中取出优先级最高的元素（也就是所谓的拥有最高优先级权的元素）。
  • 优先队列是0个或者多个元素的集合，每个元素都有一个优先权或者值， 对优先队列执行的操作有一下这些:
    
    • 1、查找；
    • 2、插入一个新的元素；
    • 3、删除；
  • 在最小优先队列（min priority queue）中， 查找操作用来搜索优先权最小的元素， 删除操作用来删除该元素；
  • 对于最大优先队列（max priority queue）中， 查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。
  • 优先权队列中的元素可以有相同的优先权，查找或删除操作可根据任意优先权进行。

---

• 优先队列的实现原理分析
  
  • 优先队列是在实际工程中被广泛应用的一种数据结构，不管是在操作系统的进程调度中，还是在相关的图算法比如Prim算法和Dijkstra算法中，都是可以看到优先队列的实现身影。
  • 优先队列：
    
    • 以操作系统的进程调度为例，比如我们在使用手机的过程中，手机分配给来电的优先级都会比其他程序高，在这个业务场景中，我们不要求所有元素全部有序，因为需要处理的只是当前键值最大的元素（优先级最高）。在这种情况，需要实现的只是删除最大的元素和插入新的元素，这种数据结构就叫做优先队列。
    • 在正式实现优先队列之前，有必要先来了解一下对于堆的相关操作。
  • 堆的基本概念：
    
    • 定义当一棵二叉树的每个结点都要大于等于它的两个结点的时候，称这棵二叉树有序。
      
  • 堆上浮和下沉操作：
    
    • 对于保证堆有序， 对于堆需要对它进行上浮和下沉操作，先来实现两个常用的工具方法，其中less()用于比较两个元素的大小，exch()用于交换数组的两个元素：

private static boolean less(Comparable[] pq, int i, int j) {
    return pq[i-1].compareTo(pq[j-1]) < 0;
    // `compareTo()` 方法用于将 `Number`对象与方法的参数进行比较。可用于比较 Byte, Long, Integer等。
    // 该方法用于两个相同数据类型的比较，两个不同类型的数据不能用此方法来比较。
    // `public int compareTo( NumberSubClass referenceName )`
    // `referenceName` -- 可以是一个 `Byte, Double, Integer, Float, Long 或 Short`类型的参数。
    // 返回值
    // 如果指定的数与参数相等返回0。
    // 如果指定的数小于参数返回 -1。
    // 如果指定的数大于参数返回 1。
}
private static void exch(Object[] pq, int i, int j) {
    Object swap = pq[i - 1];
    pq[i - 1] = pq[j - 1];
    pq[j - 1] = swap;
}

• 上浮操作：
  
  • 首先来分析一下上浮操作，以swim(5)为例子，需要来看一下上浮操作的过程。对于堆的进行的上浮操作目的是为了保持堆的有序性，即一个结点的值大于它的子结点的值，所以将我们a[5]和它的父结点a[2]想比较，如果它大于父结点的值，需要进行两者交换，然后继续进行swim(2)。
    
  • 具体的代码实现

private void swim(Comparable pq[], int k) {
    while(k > 1 && less(k/2, k)) {
        exch(k/2, k);
        k = k/2;
    }
}

• 下沉操作：
  
  • 接着就开始来分析一下下沉操作，将结点a[2]和它两个子结点中较小的结点相比较，如果小于子结点，就需要进行交换两者，然后继续sink(5)。
    
  • 代码实现：

private static void sink(Comparable pq[], int k, int n) {
    while(2*k <= n) {
        int j = 2*k;
        if (j < n && less(pq, j, j+1)) 
            j ++;
        if (!less(pq, k, j))
            break;
        exch(pq, k, j);
        k = j;
    }
}

---

JackDan9 Thinking