admin管理员组

文章数量:1623784

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

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

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

入队列

出队列

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

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

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

例如最大优先队列的最大元素是 8，那么虽然元素 8 并不是队首元素，但出队的时候仍然让元素 8 首先出队：

利用线性数据结构可以实现，但是时间复杂度较高，最坏时间复杂度 O ( n ) O(n) O(n)，并不是最理想的方式。

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

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

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

使用普通数组表示的最大优先队列：

第一次出队操作，关键字 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 层。

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。

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

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 堆的插入 - 向上调整

最小堆示例
首先在堆的末尾插入该数值，然后不断向上调整，直到没有大小颠倒为止。

最大堆示例
插入关键字数据为 5 的新节点。

关键字数据为 5 的新节点上浮到合适位置。

2.3 取出最值

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

2.4 删除最值 - 向下调整

最小堆示例
首先将堆的最后一个元素复制到根节点，并删除最后一个元素，然后将根节点不断向下进行调整直到没有大小颠倒。


最大堆示例
关键字数据为 10 的二叉堆堆顶节点出队。

关键字数据为 1 的最后一个节点替换到堆顶位置。

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

关键字数据为 1 的节点的左右孩子中值最大的节点 (关键字数据为 6)。关键字数据为 1 的节点下沉，关键字数据为 6 的节点上浮。

3. 优先队列的实现

下图堆的高度为 h = 2 h = 2 h=2 的堆有 h + 1 = 3 h+1 = 3 h+1=3 层。根节点编号为 1，不是 0。

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

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 开始，编号顺序是从上到下、从左到右，然后根据这个编号将树中的节点存储到数组中。

假设当前节点的编号 (数组中的编号) 为 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/5417.html
https://github/onnple
漫画算法:小灰的算法之旅
https://iq.opengenus/max-heap-min-heap/

本文标签： 队列优先级PriorityQueue

版权声明：本文标题：Priority Queue - 优先级队列 - 优先队列 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dianzi/1728895276a1178329.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。