第9章堆与优先队列

当前位置:

首页 > 编程开发 > 数据结构 >

第9章堆与优先队列

第9章堆与优先队列
9.1 引言
在数据处理中，“按优先级动态获取最值”是一类常见需求。例如：医院急诊系统需优先救治病情严重的患者，操作系统需调度高优先级进程占用CPU，搜索引擎需从海量结果中返回最相关的前K条记录。这些场景的核心诉求是——高效维护一组动态数据，并能快速获取和删除其中的最大（或最小）值。
普通线性结构（如数组、链表）难以满足这类需求：无序数组查找最值需O(n)，有序数组插入需O(n)。而堆（Heap）作为一种特殊的完全二叉树，通过巧妙的结构设计和调整策略，将插入和删除最值的时间复杂度均优化至O(log n)，成为实现优先队列（Priority Queue）的理想数据结构。
本章将从“优先队列的需求”出发，首先定义堆的结构特性，详解堆的插入、删除、构建等核心操作的底层原理与Python实现，进而基于堆实现优先队列，并通过“堆排序”“Top K问题”等工程案例，展示堆在实际问题中的高效应用，最终帮助读者建立“用堆解决动态最值问题”的思维框架。
9.2 堆的定义与结构特性
9.2.1 堆的两种基本类型
堆是满足“堆性质”的完全二叉树，根据堆性质的不同分为两类：
定义9.1 最大堆（Max-Heap）
对于任意节点，其父节点的值大于或等于其子节点的值，即：
parent(i)≥left(i)且parent(i)≥right(i) ext{parent}(i) geq ext{left}(i) quad ext{且} quad ext{parent}(i) geq ext{right}(i) parent(i)≥left(i)且parent(i)≥right(i)
其中，parent(i) ext{parent}(i)parent(i)表示节点iii的父节点，left(i) ext{left}(i)left(i)和right(i) ext{right}(i)right(i)分别表示左、右子节点。最大堆的根节点是整个堆中的最大值。
定义9.2 最小堆（Min-Heap）
对于任意节点，其父节点的值小于或等于其子节点的值，即：
parent(i)≤left(i)且parent(i)≤right(i) ext{parent}(i) leq ext{left}(i) quad ext{且} quad ext{parent}(i) leq ext{right}(i) parent(i)≤left(i)且parent(i)≤right(i)
最小堆的根节点是整个堆中的最小值。
示例：

最大堆结构（节点值标注）：

根节点15是最大值，每个父节点（15、10、8）均大于其子节点。

最小堆结构：

根节点2是最小值，每个父节点（2、5、3）均小于其子节点。

9.2.2 堆的数组表示
堆作为完全二叉树，可直接用数组高效存储（无需指针），通过下标计算父子节点位置，空间利用率达100%。
数组存储规则（假设数组下标从0开始）：
对于下标为iii的节点：
o左子节点下标：2i+12i + 12i+1
o右子节点下标：2i+22i + 22i+2
o父节点下标：⌊(i−1)/2⌋lfloor (i - 1) / 2 floor⌊(i−1)/2⌋（整数除法）
示例：上述最大堆的数组表示为[15,10,8,7,9,3,5]，各节点关系如下：
根节点15（i=0）：左子节点10（i=1），右子节点8（i=2）；
节点10（i=1）：左子节点7（i=3），右子节点9（i=4）；
节点8（i=2）：左子节点3（i=5），右子节点5（i=6）。
注意：若子节点下标超出数组长度，则该子节点不存在（如上述数组长度为7，i=3的右子节点下标为2*3+2=8>6，故不存在）。
9.2.3 堆的高度与节点数量
堆的高度hhh（根节点高度为0）与节点数量nnn的关系为：
h=⌊log⁡2n⌋ h = lfloor log_2 n floor h=⌊log2n⌋
例如：
n=7n=7n=7时，h=2h=2h=2（3层节点：0层1个，1层2个，2层4个）；
n=8n=8n=8时，h=3h=3h=3（4层节点：0层1个，1层2个，2层4个，3层1个）。
这一特性保证了堆的操作（插入、删除）时间复杂度为O(h)=O(log⁡n)O(h)=O(log n)O(h)=O(logn)，远优于线性结构。
9.3 堆的核心操作
以最大堆为例，详解堆的三大核心操作：插入元素、删除最大元素、构建堆。最小堆的操作仅比较方向相反，原理一致。
9.3.1 插入元素（上浮调整）
目标：向堆中插入新元素，维持最大堆的性质（父节点≥子节点）。
操作步骤：
1.添加至末尾：将新元素插入数组末尾（完全二叉树的最后一个位置）；
2.上浮调整（Bubble Up）：若新元素大于其父节点，交换两者位置，重复此过程直至父节点大于新元素或新元素成为根节点（“上浮”到正确位置）。
示例：向最大堆[15,10,8,7,9,3,5]插入元素12：
步骤1：插入末尾，数组变为[15,10,8,7,9,3,5,12]（新元素12下标为7）；
步骤2：新元素12的父节点是5（下标为(7-1)//2=3），12>5，交换→[15,10,8,7,9,3,12,5]（12下标变为6）；
新元素12的父节点是8（下标为(6-1)//2=2），12>8，交换→[15,10,12,7,9,3,8,5]（12下标变为2）；
新元素12的父节点是15（下标为(2-1)//2=0），12<15，停止调整。
调整后堆结构为：

代码实现：
python

	def max_heap_insert(heap, value): 
	"""向最大堆中插入元素，返回调整后的堆""" 
	# 步骤1：添加至末尾 
	heap.append(value) 
	# 步骤2：上浮调整 
	i = len(heap) - 1 # 新元素下标 
	while i > 0: # 未到达根节点 
	parent_i = (i - 1) // 2 # 父节点下标 
	if heap[i] > heap[parent_i]: 
	# 新元素大于父节点，交换 
	heap[i], heap[parent_i] = heap[parent_i], heap[i] 
	i = parent_i # 继续向上比较 
	else: 
	break # 父节点更大，无需继续 
	return heap

时间复杂度：O(log⁡n)O(log n)O(logn)，最多上浮hhh层（h=log⁡nh=log nh=logn）。
9.3.2 删除最大元素（下沉调整）
目标：删除堆顶元素（最大值），维持最大堆的性质。
操作步骤：
1.交换首尾元素：将堆顶元素（下标0）与数组末尾元素交换（保证完全二叉树结构不被破坏）；
2.删除末尾元素：数组长度减1（相当于删除原堆顶元素）；
3.下沉调整（Bubble Down）：从堆顶开始，比较当前节点与左右子节点，将最大的子节点与当前节点交换，重复此过程直至当前节点大于所有子节点或成为叶子节点（“下沉”到正确位置）。
示例：从最大堆[15,10,12,7,9,3,8,5]（插入12后的堆）删除堆顶15：
步骤1：交换首尾元素（15与5）→[5,10,12,7,9,3,8,15]；
步骤2：删除末尾元素15，数组变为[5,10,12,7,9,3,8]（长度7）；
步骤3：当前节点5（下标0）的左右子节点为10（下标1）和12（下标2），12最大，交换→[12,10,5,7,9,3,8]（5下沉到下标2）；
当前节点5（下标2）的左右子节点为3（下标5）和8（下标6），8最大，交换→[12,10,8,7,9,3,5]（5下沉到下标6，成为叶子节点）；
此时堆恢复平衡，最大元素为12（新堆顶）。
代码实现：
python

	def max_heap_extract_max(heap): 
	"""删除并返回最大堆的堆顶元素，维持堆性质""" 
	if not heap: 
	raise IndexError("Cannot extract from empty heap") 
	# 步骤1：交换首尾元素 
	heap[0], heap[-1] = heap[-1], heap[0] 
	# 步骤2：删除末尾元素（原堆顶） 
	max_val = heap.pop() 
	# 步骤3：下沉调整（从堆顶开始） 
	n = len(heap) 
	i = 0 # 当前节点下标 
	while True: 
	left_i = 2 * i + 1 # 左子节点下标 
	right_i = 2 * i + 2 # 右子节点下标 
	largest_i = i # 假设当前节点最大 
	
	# 找出当前节点、左子、右子中的最大值下标 
	if left_i < n and heap[left_i] > heap[largest_i]: 
	largest_i = left_i 
	if right_i < n and heap[right_i] > heap[largest_i]: 
	largest_i = right_i 
	
	if largest_i != i: 
	# 最大值不是当前节点，交换并继续下沉 
	heap[i], heap[largest_i] = heap[largest_i], heap[i] 
	i = largest_i 
	else: 
	break # 当前节点最大，无需继续 
	return max_val

时间复杂度：O(log⁡n)O(log n)O(logn)，最多下沉hhh层（h=log⁡nh=log nh=logn）。
9.3.3 构建堆（Heapify）
目标：将无序数组转化为最大堆。
核心思想：从最后一个非叶子节点开始，自底向上对每个节点执行下沉调整，直至根节点。
为什么从非叶子节点开始？
叶子节点无子女，本身已是堆；非叶子节点可能违反堆性质，需下沉调整。
最后一个非叶子节点下标：
对于长度为nnn的数组，最后一个非叶子节点下标为⌊n/2⌋−1lfloor n/2 floor - 1⌊n/2⌋−1（例如n=7n=7n=7时，⌊7/2⌋−1=3−1=2lfloor 7/2 floor -1=3-1=2⌊7/2⌋−1=3−1=2）。
示例：将无序数组[3,9,7,5,10,8,12]构建为最大堆：
步骤1：数组长度n=7n=7n=7，最后一个非叶子节点下标为⌊7/2⌋−1=2lfloor 7/2 floor -1=2⌊7/2⌋−1=2（值为7）；
步骤2：从下标2开始，自底向上遍历各节点并下沉：
oi=2（值7）：左右子节点为8（i=5）和12（i=6），12最大，交换→[3,9,12,5,10,8,7]；
oi=1（值9）：左右子节点为5（i=3）和10（i=4），10最大，交换→[3,10,12,5,9,8,7]；
oi=0（值3）：左右子节点为10（i=1）和12（i=6），12最大，交换→[12,10,3,5,9,8,7]；
oi=2（值3，交换后新位置）：左右子节点为8（i=5）和7（i=6），8最大，交换→[12,10,8,5,9,3,7]；
构建完成，数组[12,10,8,5,9,3,7]为最大堆。
代码实现：
python

	def build_max_heap(arr): 
	"""将无序数组构建为最大堆""" 
	n = len(arr) 
	# 从最后一个非叶子节点开始，自底向上下沉调整 
	for i in range(n//2 - 1, -1, -1): 
	# 对节点i执行下沉调整 
	current_i = i 
	while True: 
	left_i = 2 * current_i + 1 
	right_i = 2 * current_i + 2 
	largest_i = current_i 
	
	if left_i < n and arr[left_i] > arr[largest_i]: 
	largest_i = left_i 
	if right_i < n and arr[right_i] > arr[largest_i]: 
	largest_i = right_i 
	
	if largest_i != current_i: 
	arr[current_i], arr[largest_i] = arr[largest_i], arr[current_i] 
	current_i = largest_i 
	else: 
	break 
	return arr

时间复杂度：O(n)O(n)O(n)（而非O(nlog⁡n)O(nlog n)O(nlogn)）。证明需通过级数求和，核心思想是：底层节点多但下沉次数少，上层节点少但下沉次数多，总体复杂度线性。
9.4 优先队列及其实现
9.4.1 优先队列的定义
优先队列（Priority Queue）是一种抽象数据类型，支持两种核心操作：
入队（Insert）：添加元素到队列，按优先级排序；
出队（Extract-Max/Min）：删除并返回队列中优先级最高（或最低）的元素。
与普通队列（FIFO）不同，优先队列的元素处理顺序由优先级决定，而非入队顺序。
优先队列的实现方式：
无序数组/链表：入队O(1)O(1)O(1)，出队O(n)O(n)O(n)（需遍历找最值）；
有序数组/链表：入队O(n)O(n)O(n)（需插入到正确位置），出队O(1)O(1)O(1)；
堆：入队O(log⁡n)O(log n)O(logn)，出队O(log⁡n)O(log n)O(logn)，是最优实现方式。
9.4.2 基于堆的优先队列实现
以最大优先队列（每次出队最大值）为例，基于最大堆实现，封装堆的插入和删除操作。
代码实现：
python

	class MaxPriorityQueue: 
	def __init__(self): 
	self.heap = [] # 用数组存储堆 
	
	def insert(self, value): 
	"""入队：插入元素并维持最大堆性质""" 
	max_heap_insert(self.heap, value) 
	
	def extract_max(self): 
	"""出队：删除并返回优先级最高（最大）的元素""" 
	return max_heap_extract_max(self.heap) 
	
	def get_max(self): 
	"""查看队首：返回优先级最高的元素（不删除）""" 
	if not self.heap: 
	raise IndexError("Queue is empty") 
	return self.heap[0] 
	
	def is_empty(self): 
	"""判断队列是否为空""" 
	return len(self.heap) == 0 
	
	def size(self): 
	"""返回队列元素个数""" 
	return len(self.heap)

使用示例：
python

	# 初始化优先队列 
	pq = MaxPriorityQueue() 
	# 入队元素 
	pq.insert(5) 
	pq.insert(10) 
	pq.insert(3) 
	pq.insert(8) 
	# 查看队首 
	print("当前最高优先级元素:", pq.get_max()) # 输出：10 
	# 出队 
	print("出队元素:", pq.extract_max()) # 输出：10 
	print("当前最高优先级元素:", pq.get_max()) # 输出：8

9.4.3 最小优先队列
最小优先队列（每次出队最小值）基于最小堆实现，仅需将堆的比较方向反转（父节点≤子节点）。
最小堆的下沉调整函数（核心差异）：
python

	def min_heap_bubble_down(heap, i): 
	"""最小堆的下沉调整（用于删除最小元素）""" 
	n = len(heap) 
	while True: 
	left_i = 2 * i + 1 
	right_i = 2 * i + 2 
	smallest_i = i 
	
	if left_i < n and heap[left_i] < heap[smallest_i]: 
	smallest_i = left_i 
	if right_i < n and heap[right_i] < heap[smallest_i]: 
	smallest_i = right_i 
	
	if smallest_i != i: 
	heap[i], heap[smallest_i] = heap[smallest_i], heap[i] 
	i = smallest_i 
	else: 
	break

最小优先队列的实现与MaxPriorityQueue类似，仅需替换堆操作函数。
9.5 堆的工程应用
9.5.1 堆排序
堆排序是基于堆的特性实现的高效排序算法，时间复杂度O(nlog⁡n)O(nlog n)O(nlogn)，空间复杂度O(1)O(1)O(1)（原地排序）。
排序步骤：
1.构建最大堆：将无序数组转化为最大堆（堆顶为最大值）；
2.交换首尾元素：堆顶（最大值）与数组末尾元素交换，此时末尾为排序后的最大值；
3.缩小堆范围并下沉：堆大小减1（排除已排序的末尾元素），对新堆顶执行下沉调整；
4.重复步骤2-3：直至堆大小为1，数组完全排序（升序）。
示例：对数组[3,9,7,5,10,8,12]堆排序：
步骤1：构建最大堆→[12,10,8,5,9,3,7]（见9.3.3节示例）；
步骤2-3：交换12和7→[7,10,8,5,9,3,12]，堆大小=6，下沉7→[10,9,8,5,7,3,12]；
步骤2-3：交换10和3→[3,9,8,5,7,10,12]，堆大小=5，下沉3→[9,7,8,5,3,10,12]；
重复执行，最终数组变为[3,5,7,8,9,10,12]（升序）。
代码实现：
python

	def heap_sort(arr): 
	"""堆排序（升序）""" 
	n = len(arr) 
	# 步骤1：构建最大堆 
	build_max_heap(arr) 
	# 步骤2-3：交换首尾+下沉调整，缩小堆范围 
	for i in range(n-1, 0, -1): 
	arr[0], arr[i] = arr[i], arr[0] # 交换堆顶与末尾元素 
	# 对新堆顶（下标0）执行下沉调整，堆大小为i 
	current_i = 0 
	heap_size = i 
	while True: 
	left_i = 2 * current_i + 1 
	right_i = 2 * current_i + 2 
	largest_i = current_i 
	
	if left_i < heap_size and arr[left_i] > arr[largest_i]: 
	largest_i = left_i 
	if right_i < heap_size and arr[right_i] > arr[largest_i]: 
	largest_i = right_i 
	
	if largest_i != current_i: 
	arr[current_i], arr[largest_i] = arr[largest_i], arr[current_i] 
	current_i = largest_i 
	else: 
	break 
	return arr

堆排序的优缺点：
优点：时间复杂度稳定O(nlog⁡n)O(nlog n)O(nlogn)，空间复杂度O(1)O(1)O(1)，适合大数据量排序；
缺点：不稳定排序（相等元素可能交换位置），缓存友好性较差（堆操作访问数组下标跳跃）。
9.5.2 Top K问题
问题描述：从海量数据（nnn个元素）中找出前KKK个最大元素（K≪nK ll nK≪n），例如“从100万条订单中找出消费最高的前10名用户”。
常规解法：排序后取前KKK个，时间复杂度O(nlog⁡n)O(nlog n)O(nlogn)，但nnn过大时内存无法容纳。
堆解法（最小堆）：
1.构建最小堆：取前KKK个元素构建最小堆（堆顶为KKK个元素中的最小值）；
2.遍历剩余元素：若元素大于堆顶，替换堆顶并下沉调整（保证堆内始终是当前最大的KKK个元素）；
3.结果处理：遍历结束后，堆内KKK个元素即为前KKK个最大元素（需排序后返回，因堆内无序）。
优势：
时间复杂度O(nlog⁡K)O(nlog K)O(nlogK)（K≪nK ll nK≪n时，远优于O(nlog⁡n)O(nlog n)O(nlogn)）；
空间复杂度O(K)O(K)O(K)（仅需存储KKK个元素，适合海量数据）。
代码实现：
python

	def top_k_elements(arr, k): 
	"""从数组中找出前k个最大元素""" 
	if k <= 0 or k > len(arr): 
	raise ValueError("k must be between 1 and len(arr)") 
	# 步骤1：取前k个元素构建最小堆 
	min_heap = arr[:k] 
	# 构建最小堆（需实现最小堆的构建函数，类似build_max_heap） 
	build_min_heap(min_heap) # 假设已实现该函数 
	# 步骤2：遍历剩余元素 
	for num in arr[k:]: 
	if num > min_heap[0]: 
	min_heap[0] = num 
	min_heap_bubble_down(min_heap, 0) # 下沉调整（最小堆） 
	# 步骤3：堆内元素排序后返回（升序转降序） 
	return sorted(min_heap, reverse=True) 
	
	# 示例：找出[3,9,7,5,10,8,12]中前3个最大元素 
	print(top_k_elements([3,9,7,5,10,8,12], 3)) # 输出：[12,10,9]

9.5.3 数据流的中位数
问题描述：动态维护一组数据，支持高效插入和查询中位数（数据流场景，数据量不确定）。
堆解法：用两个堆：
最大堆（lower）：存储较小一半元素（中位数左侧），堆顶为最大值；
最小堆（upper）：存储较大一半元素（中位数右侧），堆顶为最小值；
平衡条件：len(lower)=len(upper) ext{len(lower)} = ext{len(upper)}len(lower)=len(upper) 或 len(lower)=len(upper)+1 ext{len(lower)} = ext{len(upper)} + 1len(lower)=len(upper)+1；
中位数：元素总数为奇数时，中位数为lower堆顶；为偶数时，为lower堆顶与upper堆顶的平均值。
插入步骤：
1.若元素≤lower堆顶，插入lower；否则插入upper；
2.调整两堆大小至满足平衡条件（通过移动堆顶元素）。
9.6 本章总结
堆的核心特性：完全二叉树结构，通过“上浮”和“下沉”操作维持堆性质（最大堆/最小堆），支持O(log⁡n)O(log n)O(logn)的插入和删除最值操作。
优先队列：基于堆实现，核心操作入队和出队均为O(log⁡n)O(log n)O(logn)，是动态优先级任务调度的理想选择。
堆的应用：堆排序（O(nlog⁡n)O(nlog n)O(nlogn)原地排序）、Top K问题（O(nlog⁡K)O(nlog K)O(nlogK)高效查找）、数据流中位数（动态维护）等，尤其适合“动态维护最值”场景。
堆的优势在于简单高效，但不支持随机访问和按值查找；若需综合查询能力，需结合BST等结构。理解堆的调整策略（上浮/下沉）是掌握本章的关键。
9.7 思考题
1.实现最小堆的插入、删除最小元素和构建堆操作。
2.设计一个支持修改元素优先级的优先队列（提示：需记录元素在堆中的下标，修改后执行上浮或下沉）。
3.用两个堆实现数据流的中位数查找（要求插入和查询均为O(log⁡n)O(log n)O(logn)时间复杂度）。
4.对比堆排序、快速排序、归并排序的时间复杂度、空间复杂度和稳定性。
5.用堆实现一个定时任务调度器，支持按任务的执行时间（timestamp）优先级执行任务。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49295.html

栏目列表

首页 > 编程开发 > 数据结构 >

第9章 堆与优先队列

第9章堆与优先队列