JackDan数据结构篇之优先队列

约定不等于承诺〃 2022-06-14 06:49 257阅读 0赞

# 优先队列 #

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

--------------------

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

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)`。  
        ![下沉操作图][format_png 2]
     *  **代码实现**：

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

[format_png]: /images/20220614/1cbbf67d26b74e999b18b5594376680f.png
[format_png 1]: /images/20220614/61ebc891d13d4603a76246339f7c1ff7.png
[format_png 2]: /images/20220614/bc19e508aba8439a8edd0c7dd6d83e37.png