第8章 堆与高级树结构
8.1 堆的基本概念与性质
堆（Heap）是一种特殊的完全二叉树，其核心特性是节点值与子节点值之间存在严格的大小关系。这种结构广泛应用于优先队列、排序算法等场景，能够高效地获取最大或最小元素。
8.1.1 堆的定义与分类
最大堆（Max Heap）：任意节点的值 大于等于 其左右子节点的值，根节点为整个堆的最大值。
最小堆（Min Heap）：任意节点的值 小于等于 其左右子节点的值，根节点为整个堆的最小值。
示例：

	9（最大堆） 1（最小堆） 
	/  /  
	7 6 3 2 
	/  / /  / 
	3 2 5 4 5 6

8.1.2 堆的性质
1.结构性：堆是一棵完全二叉树，因此可以用数组存储（无需指针，通过索引计算父子节点位置）。
2.堆序性：
o最大堆：对任意节点 iii，有 heap[i]≥heap[2i+1]heap[i] geq heap[2i+1]heap[i]≥heap[2i+1] 且 heap[i]≥heap[2i+2]heap[i] geq heap[2i+2]heap[i]≥heap[2i+2]（假设根节点索引为0）。
o最小堆：对任意节点 iii，有 heap[i]≤heap[2i+1]heap[i] leq heap[2i+1]heap[i]≤heap[2i+1] 且 heap[i]≤heap[2i+2]heap[i] leq heap[2i+2]heap[i]≤heap[2i+2]。
8.1.3 堆的存储结构
堆通常用数组实现，节点索引关系如下（设数组为heap，节点索引为i）：
父节点索引：parent=(i−1)//2parent = (i-1) // 2parent=(i−1)//2
左子节点索引：left=2i+1left = 2i + 1left=2i+1
右子节点索引：right=2i+2right = 2i + 2right=2i+2
示例：最大堆[9,7,6,3,2,5]的数组存储与树结构对应关系：
数组索引：0 1 2 3 4 5
值： 9 7 6 3 2 5
树结构：

	9(0) 
	/  
	7(1) 6(2) 
	/  / 
	3(3)2(4)5(5)

8.2 堆的基本操作
堆的核心操作包括插入、删除堆顶元素和堆化（调整堆结构以满足堆序性）。以最大堆为例，操作逻辑如下：
8.2.1 堆化（Heapify）
堆化是维持堆序性的核心过程，分为上浮（Up Heap） 和下沉（Down Heap） 两种：
上浮（插入后调整）
当新元素插入堆尾时，可能破坏堆序性，需通过“上浮”将其调整到正确位置：
比较新元素与父节点的值，若新元素更大（最大堆），交换两者；
重复上述过程，直到父节点更大或到达根节点。
代码实现：
python

	def heapify_up(heap: list[int], index: int):
	"""最大堆上浮操作：将index位置的元素上浮至正确位置"""
	while index > 0:
	parent = (index - 1) // 2
	if heap[index] > heap[parent]:
	heap[index], heap[parent] = heap[parent], heap[index] # 交换
	index = parent
	else:
	break # 堆序性恢复，停止上浮

下沉（删除后调整）
当堆顶元素删除后，用堆尾元素替换堆顶，可能破坏堆序性，需通过“下沉”调整：
比较当前节点与左右子节点的最大值，若当前节点更小，交换两者；
重复上述过程，直到当前节点更大或到达叶子节点。
代码实现：
python

	def heapify_down(heap: list[int], index: int, size: int):
	"""最大堆下沉操作：将index位置的元素下沉至正确位置（size为堆的有效长度）"""
	while True:
	left = 2 * index + 1
	right = 2 * index + 2
	largest = index # 初始化最大值为当前节点
	
	# 找出当前节点、左子节点、右子节点中的最大值
	if left < size and heap[left] > heap[largest]:
	largest = left
	if right < size and heap[right] > heap[largest]:
	largest = right
	
	if largest != index:
	heap[index], heap[largest] = heap[largest], heap[index] # 交换
	index = largest # 继续下沉
	else:
	break # 堆序性恢复，停止下沉

8.2.2 插入操作
1.将新元素添加到数组末尾（堆的最后一层最右侧）；
2.对新元素执行上浮操作，恢复堆序性。
代码实现：
python

	def heap_insert(heap: list[int], val: int):
	"""向最大堆中插入元素val"""
	heap.append(val) # 添加到末尾
	heapify_up(heap, len(heap)-1) # 上浮调整

8.2.3 删除堆顶元素
堆顶元素是最大堆的最大值（或最小堆的最小值），删除步骤如下：
1.用数组末尾元素替换堆顶元素；
2.删除数组末尾元素（堆大小减1）；
3.对新堆顶执行下沉操作，恢复堆序性。
代码实现：
python

	def heap_extract_max(heap: list[int]) -> int:
	"""删除并返回最大堆的堆顶元素（最大值）"""
	if not heap:
	raise IndexError("Heap is empty")
	max_val = heap[0]
	heap[0] = heap[-1] # 末尾元素替换堆顶
	heap.pop() # 删除末尾元素
	heapify_down(heap, 0, len(heap)) # 下沉调整
	return max_val

8.2.4 建堆
将无序数组转换为堆的过程称为“建堆”，从最后一个非叶子节点开始，依次对每个节点执行下沉操作。
示例：无序数组[3,2,5,7,6,9]建最大堆的过程：
1.最后一个非叶子节点索引为 (n//2)−1=(6//2)−1=2(n//2)-1 = (6//2)-1 = 2(n//2)−1=(6//2)−1=2（值为5）；
2.对索引2、1、0依次执行下沉，最终得到堆[9,7,5,3,2,6]。
代码实现：
python

	def build_heap(arr: list[int]) -> list[int]:
	"""将无序数组转换为最大堆"""
	size = len(arr)
	# 从最后一个非叶子节点开始下沉
	for i in range(size//2 - 1, -1, -1):
	heapify_down(arr, i, size)
	return arr

8.3 堆排序
堆排序是利用堆结构实现的高效排序算法，时间复杂度为 O(nlog⁡n)O(nlog n)O(nlogn)，步骤如下：
1.建堆：将无序数组转换为最大堆（升序排序）；
2.排序：
o交换堆顶（最大值）与数组末尾元素；
o堆大小减1，对新堆顶执行下沉操作；
o重复上述过程，直到堆大小为1。
代码实现：
python

	def heap_sort(arr: list[int]) -> list[int]:
	"""堆排序（升序）"""
	size = len(arr)
	# 步骤1：建最大堆
	build_heap(arr)
	
	# 步骤2：排序
	for i in range(size-1, 0, -1):
	arr[0], arr[i] = arr[i], arr[0] # 堆顶与末尾元素交换
	heapify_down(arr, 0, i) # 对0~i-1范围下沉（堆大小为i）
	return arr

示例：对[3,2,5,7,6,9]堆排序：
建堆后：[9,7,5,3,2,6]；
交换堆顶与末尾（9和6），调整堆：[7,6,5,3,2 | 9]；
重复后最终得到升序数组[2,3,5,6,7,9]。
8.4 堆的应用
堆的高效插入/删除特性使其在以下场景中广泛应用：
8.4.1 优先队列
优先队列（Priority Queue）是一种特殊队列，每次出队的是优先级最高的元素（如最大值或最小值）。堆是实现优先队列的理想结构：
入队：堆插入操作（O(log⁡n)O(log n)O(logn)）；
出队：删除堆顶操作（O(log⁡n)O(log n)O(logn)）；
应用：任务调度（优先处理高优先级任务）、Dijkstra最短路径算法（快速获取当前最短路径节点）。
8.4.2 Top K问题
从海量数据中找出最大的K个元素（如“前100名成绩”“热门商品Top10”），利用小顶堆可高效解决：
1.用前K个元素构建大小为K的小顶堆（堆顶为当前K个元素的最小值）；
2.遍历剩余元素，若元素大于堆顶，则替换堆顶并下沉调整；
3.遍历结束后，堆中元素即为最大的K个元素。
优势：时间复杂度 O(nlog⁡K)O(nlog K)O(nlogK)，空间复杂度 O(K)O(K)O(K)，适合处理大数据。
8.4.3 中位数查找
中位数是有序序列中中间位置的数，利用两个堆可动态维护中位数：
大顶堆存储序列左半部分（较小元素），堆顶为左半部分最大值；
小顶堆存储序列右半部分（较大元素），堆顶为右半部分最小值；
插入元素时平衡两个堆的大小（差不超过1），中位数为大顶堆堆顶（奇数个元素）或两堆顶平均值（偶数个元素）。
8.5 高级树结构：B树
B树（B-Tree）是一种多路平衡查找树，专为磁盘等外存储设备设计，通过降低树高减少I/O次数（相比二叉树，B树每个节点可存储多个关键字，树高更低）。
8.5.1 B树的定义与特性
阶数（m）：每个节点最多有 m−1m-1m−1 个关键字和 mmm 个子树（m≥2m geq 2m≥2）。
平衡条件：
o根节点至少有2个子树（除非为空树或只有一个节点）；
o非根节点至少有 ⌈m/2⌉lceil m/2 ceil⌈m/2⌉ 个子树；
o所有叶子节点在同一层（深度相同）。
关键字有序：每个节点的关键字按升序排列，且子树与关键字一一对应（如关键字 k1<k2<...<knk_1 < k_2 < ... < k_nk1​<k2​<...<kn​，则子树 T0T_0T0​ 中所有关键字 < k1k_1k1​，T1T_1T1​ 中关键字在 k1k_1k1​ 和 k2k_2k2​ 之间，以此类推）。
示例：3阶B树（m=3，每个节点最多2个关键字、3个子树）：

	[30, 60] 
	/ |  
	[10,20] [40,50] [70,80]

8.5.2 B树的插入与分裂
插入关键字时，若节点关键字数达到 m−1m-1m−1，需执行分裂（Split）操作维持平衡：
1.将节点从中间关键字处分为左、右两个节点；
2.中间关键字上升到父节点；
3.若父节点也满，则继续分裂，直到根节点（根节点分裂会使树高+1）。
8.5.3 B树的应用
B树主要用于数据库索引和文件系统，例如：
MySQL的InnoDB存储引擎使用B树（聚簇索引）；
特点：查询效率高（树高低），支持范围查询（通过关键字有序性）。
8.6 高级树结构：B+树
B+树是B树的变体，在数据库索引中应用更广泛，其核心改进是所有关键字存储在叶子节点，且叶子节点形成有序链表。
8.6.1 B+树的特性
非叶子节点仅作索引：不存储数据，仅存储关键字和子树指针；
叶子节点有序链表：所有叶子节点通过指针连接，支持高效范围查询（无需回溯父节点）；
平衡条件：与B树类似，但叶子节点必须在同一层。
示例：3阶B+树：
非叶子节点：

	[30, 60] 
	/ |  
	[10,20] [40,50] [70,80] 
	叶子节点（有序链表）：10 → 20 → 30 → 40 → 50 → 60 → 70 → 80

8.6.2 B+树 vs B树

	[1+3+5+7+9=25] 
	/  
	[1+3+5=9] [7+9=16] 
	/  /  
	[1+3=4] [5] [7] [9] 
	/  
	[1] [3]

区间查询：查询[1,3]（索引1到3，值3+5+7=15）：
根节点区间[0,4]，左子树[0,2]与查询重叠，右子树[3,4]与查询重叠；
递归查询左子树[0,2]的右子树[2,2]（值5），右子树[3,4]的左子树[3,3]（值7），加上中间节点[1,1]（值3），总和3+5+7=15。
8.7.2 线段树的应用
区间统计：如求区间和、最大值、最小值；
动态更新：如实时数据监控（温度、股票价格）的区间查询；
算法优化：如区间覆盖问题、LIS（最长递增子序列）优化。
8.8 总结
本章介绍了堆和多种高级树结构，核心要点如下：
堆是完全二叉树，通过上浮/下沉维持堆序性，适合优先队列、堆排序、Top K问题；
B树和B+树是多路平衡查找树，B+树因叶子节点链表结构更适合数据库索引；
线段树专注于区间查询与更新，是处理区间问题的高效工具。
这些结构的设计均围绕“降低操作复杂度”目标，实际应用中需根据场景选择：堆适合动态最值获取，B树/B+树适合外存索引，线段树适合区间操作。
第8章 堆与高级树结构
8.1 堆的基本概念与性质
堆（Heap）是一种特殊的完全二叉树，其核心特征是节点值与子节点值之间存在严格的大小关系，适用于高效获取最值元素的场景。
8.1.1 堆的定义与分类
最大堆（Max Heap）：任意节点的值大于等于其左右子节点的值，根节点为堆中最大值。
最小堆（Min Heap）：任意节点的值小于等于其左右子节点的值，根节点为堆中最小值。
示例：
最大堆结构： 最小堆结构：

	9 1 
	/  /  
	7 6 3 2 
	/  / /  / 
	3 2 5 4 5 6

8.1.2 堆的性质
1.结构性：堆是一棵完全二叉树，因此可直接用数组存储（无需指针），通过索引计算父子节点位置。
2.堆序性：
o最大堆：对任意节点 iii，满足 heap[i]≥heap[2i+1]heap[i] geq heap[2i+1]heap[i]≥heap[2i+1] 且 heap[i]≥heap[2i+2]heap[i] geq heap[2i+2]heap[i]≥heap[2i+2]（根节点索引为0）。
o最小堆：对任意节点 iii，满足 heap[i]≤heap[2i+1]heap[i] leq heap[2i+1]heap[i]≤heap[2i+1] 且 heap[i]≤heap[2i+2]heap[i] leq heap[2i+2]heap[i]≤heap[2i+2]。
8.1.3 堆的存储结构
堆的数组存储方式如下（设数组为heap，节点索引为i）：
父节点索引：parent=(i−1)//2parent = (i-1) // 2parent=(i−1)//2
左子节点索引：left=2i+1left = 2i + 1left=2i+1
右子节点索引：right=2i+2right = 2i + 2right=2i+2
示例：最大堆[9,7,6,3,2,5]的数组与树结构对应关系：
数组索引：0 1 2 3 4 5
值： 9 7 6 3 2 5
树结构：
9(0) ← 根节点（最大值）
/
7(1) 6(2)
/ /
3(3)2(4)5(5) ← 叶子节点
8.2 堆的基本操作
堆的核心操作围绕维持“堆序性”展开，包括堆化（调整结构）、插入、删除堆顶元素。以最大堆为例，操作逻辑如下：
8.2.1 堆化（Heapify）
堆化是修复堆序性的基础操作，分为上浮（插入后调整）和下沉（删除后调整）两种：
上浮（Up Heap）
当新元素插入堆尾时，若其值大于父节点，需通过“上浮”交换至正确位置：
1.比较当前节点与父节点值；
2.若当前节点值更大，交换两者；
3.重复步骤1~2，直至父节点值更大或到达根节点。
代码实现：
python

	def heapify_up(heap: list[int], index: int):
	"""最大堆上浮：将index位置元素调整至正确位置"""
	while index > 0: # 未到达根节点
	parent = (index - 1) // 2
	if heap[index] > heap[parent]:
	heap[index], heap[parent] = heap[parent], heap[index] # 交换
	index = parent # 继续向上比较
	else:
	break # 堆序性恢复，停止

下沉（Down Heap）
当堆顶元素被替换为较小值时，需通过“下沉”交换至正确位置：
1.比较当前节点与左右子节点的最大值；
2.若当前节点值更小，与最大值节点交换；
3.重复步骤1~2，直至当前节点值最大或到达叶子节点。
代码实现：
python

	def heapify_down(heap: list[int], index: int, size: int):
	"""最大堆下沉：将index位置元素调整至正确位置（size为堆有效长度）"""
	while True:
	left = 2 * index + 1 # 左子节点索引
	right = 2 * index + 2 # 右子节点索引
	largest = index # 初始化最大值为当前节点
	
	# 找出当前节点、左子节点、右子节点中的最大值
	if left < size and heap[left] > heap[largest]:
	largest = left
	if right < size and heap[right] > heap[largest]:
	largest = right
	
	if largest != index: # 当前节点非最大值，需交换
	heap[index], heap[largest] = heap[largest], heap[index]
	index = largest # 继续向下比较
	else:
	break # 堆序性恢复，停止

8.2.2 插入操作
1.将新元素添加至数组末尾（堆的最后一层最右侧）；
2.对新元素执行上浮操作，恢复堆序性。
代码实现：
python

	def heap_insert(heap: list[int], val: int):
	"""向最大堆插入元素val"""
	heap.append(val) # 新增元素至末尾
	heapify_up(heap, len(heap)-1) # 上浮调整

8.2.3 删除堆顶元素
堆顶元素是最大堆的最大值，删除步骤如下：
1.用数组末尾元素替换堆顶元素；
2.删除数组末尾元素（堆大小减1）；
3.对新堆顶执行下沉操作，恢复堆序性。
代码实现：
python

	def heap_extract_max(heap: list[int]) -> int:
	"""删除并返回最大堆的堆顶元素（最大值）"""
	if not heap:
	raise IndexError("堆为空，无法删除")
	max_val = heap[0] # 堆顶为最大值
	heap[0] = heap[-1] # 末尾元素替换堆顶
	heap.pop() # 删除末尾元素
	heapify_down(heap, 0, len(heap)) # 下沉调整
	return max_val

8.2.4 建堆
将无序数组转换为堆的过程称为“建堆”，从最后一个非叶子节点开始，依次对每个节点执行下沉操作：
代码实现：
python

	def build_heap(arr: list[int]) -> list[int]:
	"""将无序数组转换为最大堆"""
	size = len(arr)
	# 从最后一个非叶子节点开始下沉（索引：size//2 - 1）
	for i in range(size//2 - 1, -1, -1):
	heapify_down(arr, i, size)
	return arr

示例：无序数组[3,2,5,7,6,9]建堆后：
初始数组：[3,2,5,7,6,9]
最后一个非叶子节点索引：2（值5），依次对索引2、1、0执行下沉：
→ 处理索引2（5）：无需调整；
→ 处理索引1（2）：下沉后数组变为[3,7,5,2,6,9]；
→ 处理索引0（3）：下沉后数组变为[9,7,5,2,6,3]（最大堆）。
8.3 堆排序
堆排序是利用堆结构实现的高效排序算法，时间复杂度 O(nlog⁡n)O(nlog n)O(nlogn)，步骤如下：
1.建堆：将无序数组转换为最大堆（升序排序）；
2.排序：
o交换堆顶（最大值）与数组末尾元素；
o堆大小减1，对新堆顶执行下沉操作；
o重复上述过程，直至堆大小为1。
代码实现：
python

	def heap_sort(arr: list[int]) -> list[int]:
	"""堆排序（升序）"""
	size = len(arr)
	# 步骤1：建最大堆
	build_heap(arr)
	
	# 步骤2：排序（每次将最大值交换至末尾）
	for i in range(size-1, 0, -1):
	arr[0], arr[i] = arr[i], arr[0] # 堆顶与末尾元素交换
	heapify_down(arr, 0, i) # 对0~i-1范围下沉（堆大小为i）
	return arr

示例：对[3,2,5,7,6,9]堆排序：
建堆后：[9,7,5,2,6,3]；
第1次交换：[3,7,5,2,6 | 9]（9已排序），下沉后堆为[7,6,5,2,3]；
第2次交换：[3,6,5,2 | 7,9]，下沉后堆为[6,3,5,2]；
最终结果：[2,3,5,6,7,9]（升序）。
8.4 堆的应用
堆的高效插入/删除特性使其在动态最值场景中广泛应用：
8.4.1 优先队列
优先队列是一种特殊队列，每次出队优先级最高的元素（如最大值），堆是其理想实现：
入队：堆插入操作（O(log⁡n)O(log n)O(logn)）；
出队：删除堆顶操作（O(log⁡n)O(log n)O(logn)）；
应用：任务调度（优先处理高优先级任务）、Dijkstra最短路径算法（快速获取当前最短路径节点）。
8.4.2 Top K问题
从海量数据中找出最大的K个元素（如“前100名成绩”），利用小顶堆可高效解决：
1.用前K个元素构建大小为K的小顶堆（堆顶为当前K个元素的最小值）；
2.遍历剩余元素，若元素大于堆顶，则替换堆顶并下沉调整；
3.遍历结束后，堆中元素即为最大的K个元素（时间复杂度 O(nlog⁡K)O(nlog K)O(nlogK)）。
8.4.3 中位数查找
动态维护数据流的中位数，可通过两个堆实现：
大顶堆存储较小一半元素（堆顶为较小元素的最大值）；
小顶堆存储较大一半元素（堆顶为较大元素的最小值）；
插入时平衡两堆大小（差不超过1），中位数为大顶堆堆顶（奇数个元素）或两堆顶平均值（偶数个元素）。
8.5 高级树结构：B树
B树（B-Tree）是一种多路平衡查找树，专为磁盘等外存储设备设计，通过降低树高减少I/O次数（相比二叉树，每个节点可存储多个关键字）。
8.5.1 B树的定义与特性
阶数（m）：每个节点最多有 m−1m-1m−1 个关键字和 mmm 个子树（m≥2m geq 2m≥2）。
平衡条件：
o根节点至少有2个子树（除非为空或仅一个节点）；
o非根节点至少有 ⌈m/2⌉lceil m/2 ceil⌈m/2⌉ 个子树；
o所有叶子节点在同一层（深度相同）。
关键字有序：节点内关键字升序排列，子树与关键字一一对应（如关键字 k1<k2<...<knk_1 < k_2 < ... < k_nk1​<k2​<...<kn​，则子树 TiT_iTi​ 中关键字在 kik_iki​ 与 ki+1k_{i+1}ki+1​ 之间）。
示例：3阶B树（m=3，最多2个关键字、3个子树）：

	[30, 60] ← 根节点（2个关键字，3个子树） 
	/ |  
	[10,20] [40,50] [70,80] ← 叶子节点（同一层）

8.5.2 B树的插入与分裂
插入关键字时，若节点关键字数达到 m−1m-1m−1，需执行分裂操作维持平衡：
1.将节点从中间关键字处分为左、右两节点；
2.中间关键字上升至父节点；
3.若父节点也满，则递归分裂，直至根节点（根节点分裂使树高+1）。
示例：3阶B树插入关键字55（原节点[40,50]已满）：
分裂[40,50]为[40]和[50]，中间关键字45上升至父节点；
父节点[30,60]变为[30,45,60]（满），继续分裂为[30]和[60]，中间关键字45成为新根；
最终树高+1，根节点为[45]，左右子树为[30]和[60]。
8.5.3 B树的应用
B树主要用于数据库索引和文件系统（如MySQL的InnoDB存储引擎），核心优势：
低树高：减少磁盘I/O次数（一次节点访问对应一次磁盘读取）；
高效查找：关键字有序，支持二分查找。
8.6 高级树结构：B+树
B+树是B树的变体，在数据库索引中应用更广泛，核心改进是所有关键字存储在叶子节点，且叶子节点形成有序链表。
8.6.1 B+树的特性
非叶子节点仅作索引：不存储数据，仅存储关键字和子树指针；
叶子节点有序链表：所有叶子节点通过指针连接，支持高效范围查询（无需回溯父节点）；
平衡条件：与B树类似，但叶子节点必须在同一层。
示例：3阶B+树（关键字仅在叶子节点存储）：
非叶子节点（索引层）：

	[30, 60] 
	/ |  
	[10,20] [40,50] [70,80] 
	叶子节点（数据层，有序链表）：10 → 20 → 30 → 40 → 50 → 60 → 70 → 80

8.6.2 B+树 vs B树

结论：B+树更适合数据库索引，尤其是范围查询频繁的场景（如“查询成绩60~80的学生”）。
8.7 高级树结构：线段树
线段树（Segment Tree）是一种用于区间查询与更新的二叉树，每个节点代表一个区间，支持高效的区间求和、最大值/最小值查询等操作。
8.7.1 线段树的结构与操作
区间划分：根节点代表整个区间，每个节点分为左右两个子区间（通常等分），叶子节点代表单个元素。
核心操作：
o区间查询：如查询[l, r]的和，递归判断当前区间与查询区间的重叠关系，合并重叠部分结果；
o单点更新：更新某个元素值，并回溯更新所有包含该元素的区间节点。
示例：对数组[1,3,5,7,9]构建线段树（区间和）：

	[0-4:25] ← 根节点（总和1+3+5+7+9=25） 
	/  
	[0-2:9] [3-4:16] ← 左子区间和1+3+5=9，右子区间和7+9=16 
	/  /  
	[0-1:4] [2:5] [3:7] [4:9] ← 叶子节点（单个元素） 
	/  
	[0:1] [1:3]

区间查询：查询[1,3]（索引1到3，值3+5+7=15）：
根节点区间[0-4]，左子树[0-2]与查询重叠，右子树[3-4]与查询重叠；
左子树[0-2]的右子节点[2:5]（值5）、右子树[3-4]的左子节点[3:7]（值7），加上中间节点[1:3]（值3），总和3+5+7=15。
8.7.2 线段树的应用
区间统计：如求区间和、最大值、最小值（时间复杂度 O(log⁡n)O(log n)O(logn)）；
动态更新：如实时数据监控（温度、股票价格）的区间查询；
算法优化：如区间覆盖问题、LIS（最长递增子序列）优化。
8.8 总结
本章介绍了堆和三类高级树结构，核心要点如下：
堆：完全二叉树，通过上浮/下沉维持堆序性，适合优先队列、堆排序、Top K问题；
B树/B+树：多路平衡查找树，B+树叶子节点链表支持高效范围查询，是数据库索引的核心结构；
线段树：专注区间查询与更新，通过区间划分实现高效的动态数据统计。
这些结构的设计均围绕“降低操作复杂度”目标，实际应用中需根据场景选择：堆适合动态最值，B+树适合外存索引，线段树适合区间操作。

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