Priority Queue - 优先级队列 - 优先队列

r囧r小猫 2022-10-30 01:26 200阅读 0赞

# **Priority Queue - 优先级队列 - 优先队列** #

## 1. 优先队列 (priority queue) 与队列 (queue) ##

队列是一种先进先出 (First Input First Output，FIFO) 的数据结构，元素在队列尾追加，而从队列头删除。

**入队列**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]  
**出队列**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

优先队列的元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out) 的行为特征。通常采用二叉堆 (heap) 数据结构来实现。

优先级队列是不同于先进先出队列的另一种队列，每次从队列中取出的是具有最高优先权的元素。

在最小优先队列 (min priority queue) 中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素。最小优先队列，无论入队顺序，当前最小的元素优先出队。  
在最大优先队列 (max priority queue) 中，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。最大优先队列，无论入队顺序，当前最大的元素优先出队。  
对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

例如最大优先队列的最大元素是 8，那么虽然元素 8 并不是队首元素，但出队的时候仍然让元素 8 首先出队：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]  
利用线性数据结构可以实现，但是时间复杂度较高，最坏时间复杂度 O ( n ) O(n) O(n)，并不是最理想的方式。

优先队列 (priority queue) 类似于队列 (queue)。队列是一种简单的数据结构，特点是先进先出。优先队列的元素正常入队，按照优先级的大小进行出队。

堆是与优先队列不同的数据结构。优先队列可以等同于堆，因为堆是用来实现优先队列的。

![在这里插入图片描述][20210216212356164.png_pic_center]

在优先队列中，每个记录保存一个优先级值或关键字，任意记录正常从队尾入队，按照优先级大小或关键字的大小进行出队。最大关键字先出队，称为最大优先队列或降序优先队列。最小关键字先出队，称为最小优先队列或升序优先队列。

使用普通数组表示的最大优先队列：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]

第一次出队操作，关键字 12 最大，所以 12 先出队。第二次进行出队操作，此时 11 最大，所以 11 出队。如果遇到关键字相等的情况，则按照它们在队中的位置进行出队。

堆可以实现性能较好的优先队列，取出效率可达到  O ( 1 ) O(1) O(1)，一般的操作都能达到  O ( log ⁡ 2 n ) O(\\log\_2^n) O(log2n)。

堆排序通常使用堆实现，堆是优先级队列的实现。

C++ STL 中的 `priority_queue` 实现了优先队列。

## 2. 堆和二叉堆 (binary heap) ##

堆主要用来实现优先队列，二叉堆是堆的一种。堆是一颗完全二叉树，也就是一棵二叉树，在叶子上从左到右被完全填满元素，结点中至少包括优先级值或关键字。父节点是其所有子孙节点的最值。

堆的主要特点是：任意结点的关键字大于或等于 (小于或等于) 儿子结点。最大堆 (max heap) 结点的关键字大于或等于儿子结点。最小堆 (min heap) 结点关键字小于或等于儿子结点，这个特点称为堆的有序性。

二叉堆的插入 (节点上浮) 和删除 (节点下沉) 的时间复杂度为  O ( log ⁡ ⁡ 2 n ) O(\\log⁡\_2^n) O(log⁡2n)，等同于优先队列的入队和出队时间复杂度。

一个高度为  h h h 的堆有  h + 1 h+1 h\+1 层。下图堆的高度为  h = 2 h = 2 h=2 的堆有  h + 1 = 3 h+1 = 3 h\+1=3 层。  
![在这里插入图片描述][20210216212602201.png_pic_center]

2^0 = 1
    2^1 = 2
    2^2 = 4
    2^3 = 8
    ……
    2^h = 2^h

如果最下面的一层已经填满，那么那一层包含  2 h 2^h 2h 个节点。树中这一层以上所有的节点数目为  2 h − 1 2^h - 1 2h−1。所以整个堆中的节点数目为： 2 ( h + 1 ) − 1 2^\{(h+1)\} - 1 2(h\+1)−1。

二叉堆是堆的最简单形式，设二叉堆的高度为  h h h，二叉堆的所有叶子结点位于第  h h h 层或第  h − 1 h-1 h−1 层 ( h > 0 h > 0 h>0)，高度为  h h h 的二叉堆有  2 h 2^h 2h 到  2 ( h + 1 ) − 1 2^\{(h+1)\}-1 2(h\+1)−1 个结点。如果一个堆有  n n n 个节点，它的高度是  h = floor ( log ⁡ 2 n ) h = \\text\{floor\}(\\log\_2^n) h=floor(log2n)。

### 2.1 二叉堆和对应的数组 ###

采用数组来存储二叉堆的元素。

下图堆的高度为  h = 2 h = 2 h=2 的堆有  h + 1 = 3 h+1 = 3 h\+1=3 层。根节点编号为 1，不是 0。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]

上图是一个最小堆，任意结点关键字小于或等于孩子结点。给堆中的结点从左到右加上索引，对应于数组中的索引和关键字。二叉堆使用数组表示的一种常见形式，得出二叉堆的逻辑定义如下：

n n n 个元素序列  k 1 , k 2 , … , k i , … , k n \{k\_1, k\_2, …, k\_i, …, k\_n\} k1,k2,…,ki,…,kn， k k k 为关键字或优先级值， i i i 为元素的索引。  
任取  i i i 属于  1 , 2 , 3 , … , n / 2 \{1, 2, 3, …, n/2\} 1,2,3,…,n/2。  
最小堆表示为： k i < = k 2 i ， k i < = k ( 2 i + 1 ) k\_i <= k\_\{2i\}，k\_i <= k\_\{(2i+1)\} ki<=k2i，ki<=k(2i\+1)。  
最大堆表示为： k i > = k 2 i ， k i > = k ( 2 i + 1 ) k\_i >= k\_\{2i\}，k\_i >= k\_\{(2i+1)\} ki>=k2i，ki>=k(2i\+1)。

上面定义数组索引从 1 开始，也可以从 0 开始。两者的区别是，使用 0 开始需要对 0 进行检测。若使用 1 开始，最大堆第 1 个放一个极大的值，最小堆放一个极小的值，因为使用数组表示二叉堆，所以堆的大小需要预先进行预测。

**建议定义数组索引从 1 开始。**

用数组表示树的关键是使用下标来寻找某个特定值的双亲和孩子，C 语言的数组下标从 0 开始。

#### 数组形式的二叉堆 - 树的根节点在数组中的索引为 1 ####

节点 `N` 的双亲是节点 `N / 2`。  
节点 `N` 的左孩子是节点 `2N`。  
书点 `N` 的右孩子是节点 `2N+1`。  
双亲节点的公式是成立的，因为整除操作符将截去小数部分。数组声明的长度比宣称的长度大 1，它的第 1 个元素被忽略。

#### 数组形式的二叉堆 - 树的根节点在数组中的索引为 0 ####

节点 `N` 的双亲节点是节点 `(N + 1) / 2 - 1 = (N + 1) / 2 - 2 / 2 = (N - 1) / 2`。  
节点 `N` 的左孩子节点是节点 `2N + 1`。  
节点 `N` 的右孩子节点是节点 `2N + 2`。

数组索引从第 0 个开始，结点间的索引关系为：  
 i i i 为第  i i i 个结点，根结点没有父结点。  
父结点索引为： ( i − 1 ) / 2 (i - 1) / 2 (i−1)/2  
左结点索引为： 2 ∗ i + 1 2 \* i + 1 2∗i\+1  
右结点索引为： 2 ∗ i + 2 2 \* i + 2 2∗i\+2

*  最大堆的堆顶是整个堆中的最大元素
 *  最小堆的堆顶是整个堆中的最小元素

可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

### 2.2 堆的插入 - 向上调整 ###

**最小堆示例**  
首先在堆的末尾插入该数值，然后不断向上调整，直到没有大小颠倒为止。  
![在这里插入图片描述][20210216221209909.png_pic_center]  
![在这里插入图片描述][20210216221336586.png_pic_center]

**最大堆示例**  
插入关键字数据为 5 的新节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]

关键字数据为 5 的新节点上浮到合适位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]

### 2.3 取出最值 ###

最值就在堆顶，即二叉树的第一个元素。

### 2.4 删除最值 - 向下调整 ###

**最小堆示例**  
首先将堆的最后一个元素复制到根节点，并删除最后一个元素，然后将根节点不断向下进行调整直到没有大小颠倒。  
![在这里插入图片描述][20210216221209909.png_pic_center]  
![在这里插入图片描述][20210216221931668.png_pic_center]  
**最大堆示例**  
关键字数据为 10 的二叉堆堆顶节点出队。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]

关键字数据为 1 的最后一个节点替换到堆顶位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 8]

关键字数据为 1 的节点的**左右孩子中值最大的节点** (关键字数据为 9)。关键字数据为 1 的节点下沉，关键字数据为 9 的节点成为新堆顶。

关键字数据为 1 的节点的**左右孩子中值最大的节点** (关键字数据为 6)。关键字数据为 1 的节点下沉，关键字数据为 6 的节点上浮。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 9]

## 3. 优先队列的实现 ##

完全二叉树可以通过数组实现，将完全二叉树中的每个节点进行编号，编号从 1 开始，编号顺序是从上到下、从左到右，然后根据这个编号将树中的节点存储到数组中。

假设当前节点的编号 (数组中的编号) 为  i i i，则有：

*  它的父节点的编号为： i / 2 i / 2 i/2 (整除)
 *  它的左孩子节点的编号为： 2 ∗ i 2 ∗ i 2∗i
 *  它的右孩子节点的编号为： 2 ∗ i + 1 2 ∗ i + 1 2∗i\+1

### 3.1 Example ###

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2019 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    // min heap in C/C++
    #include <stdio.h>
    
    #define MAX_NODE_NUM 1024
    
    int heap_array[MAX_NODE_NUM];
    int heap_size;  // init()
    
    void init()
    {
    	heap_size = 0;
    }
    
    // insert end
    void min_heap_push_up_adjust(const int data)
    {
    	++heap_size;
    	// 新节点插入到数组最后一个有效数据的后一个位置，即二叉堆的末尾插入该节点
    	int idx = heap_size;  // idx - 新节点编号
    	int parent_idx;
    
    	// 向上调整，只有 idx > 1 时才会有父节点
    	while (idx > 1)
    	{
    		parent_idx = idx / 2;  // parent_idx - 父节点编号
    
    		 // 没有上下颠倒，则结束调整
    		if (heap_array[parent_idx] <= data)
    		{
    			break;
    		}
    
    		heap_array[idx] = heap_array[parent_idx];  // 大小颠倒，则当前节点上浮
    		idx = parent_idx;
    	}
    
    	heap_array[idx] = data;
    }
    
    // delete start
    int min_heap_pop_down_adjust()
    {
    	const int result = heap_array[1];  // 获取最值
    	const int data = heap_array[heap_size];  // 等同于最后的一个元素放到根节点
    	--heap_size;
    
    	int index = 1;
    	// 必须要有孩子节点
    	while (2 * index <= heap_size)
    	{
    		int left_son_idx = 2 * index;
    		int right_son_idx = 2 * index + 1;
    
    		// 比较孩子节点的最值
    		int min_idx = left_son_idx;
    		if ((right_son_idx <= heap_size) && (heap_array[right_son_idx] < heap_array[left_son_idx]))
    		{
    			min_idx = right_son_idx;
    		}
    
    		// 没有上下颠倒，则结束调整
    		// min heap: 父节点比最小的孩子节点大，则下沉
    		// max heap: 父节点比最大的孩子节点小，则下沉
    		if (heap_array[min_idx] >= data)
    		{
    			break;
    		}
    
    		// 大小颠倒，则当前节点上沉
    		heap_array[index] = heap_array[min_idx];
    		index = min_idx;
    	}
    
    	heap_array[index] = data;
    
    	return result;
    }
    
    void build_heap(const int raw_data[], const int n)
    {
    	heap_size = 0;
    	for (int i = 1; i <= n; ++i)
    	{
    		min_heap_push_up_adjust(raw_data[i]);
    	}
    }
    
    void display_heap(const int heap_array[], const int heap_size)
    {
    	for (int i = 1; i <= heap_size; ++i)
    	{
    		printf("%d ", heap_array[i]);
    	}
    	printf("\n");
    }
    
    int main()
    {
    	int N = 9;  // 不包含 index = 0 的数据
    	int raw_data[MAX_NODE_NUM] = { 0, 9, 7, 10, 4, 5, 19, 23, 6, 7 };
    	printf("raw data:\n");
    	display_heap(raw_data, N);
    
    	init();
    	build_heap(raw_data, N);
    
    	printf("min heap data:\n");
    	display_heap(heap_array, heap_size);
    
    	return 0;
    }
    
    /*
    raw data:
    9 7 10 4 5 19 23 6 7
    min heap data:
    4 5 10 6 7 19 23 9 7
    请按任意键继续. . .
    
    */

raw data:
    9 7 10 4 5 19 23 6 7
    min heap data:
    4 5 10 6 7 19 23 9 7
    请按任意键继续. . .

## References ##

[https://www.cxyxiaowu.com/5417.html][https_www.cxyxiaowu.com_5417.html]  
[https://github.com/onnple][https_github.com_onnple]  
漫画算法:小灰的算法之旅  
[https://iq.opengenus.org/max-heap-min-heap/][https_iq.opengenus.org_max-heap-min-heap]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/f553ce8217f3422fab957494693e9b0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/7ac8fb991fdc415392c868d9eea6111a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/12251b3bdfbe4ab2a50a87d8cf752ba6.png
[20210216212356164.png_pic_center]: /images/20221024/39174b86c9ca43a98220d6ce94fc46d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221024/001edc8dbce74088a7f3f7d36d337bc0.png
[20210216212602201.png_pic_center]: /images/20221024/1951d5ea9cc1440ea07a49fffcb1fff3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221024/8ed457948f2f42eaba3bb595d9f96e64.png
[20210216221209909.png_pic_center]: /images/20221024/4e99d67a39fb4cc2bb3e4ea83967d9a2.png
[20210216221336586.png_pic_center]: /images/20221024/425700b8a21a456fa8a31ff69dfa1420.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221024/d41d62c038974fa195503f272df84e29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221024/41dfc109300e4aaebb236da8ed45142e.png
[20210216221931668.png_pic_center]: /images/20221024/9bd6624ca67f4a10886fbc253075f877.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221024/be616aed7cfa4c62b424ac414143be18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221024/f1c3b7b214824559a7a9eb4b9b14e3a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221024/3e2833f66ab74979a6cf19d5e55ff4a1.png
[https_www.cxyxiaowu.com_5417.html]: https://www.cxyxiaowu.com/5417.html
[https_github.com_onnple]: https://github.com/onnple
[https_iq.opengenus.org_max-heap-min-heap]: https://iq.opengenus.org/max-heap-min-heap/