当前位置：首页 > news >正文

堆是一种特殊的完全二叉树结构，用于高效实现优先队列

news 2026/8/31 10:26:55

堆是一种特殊的完全二叉树结构，用于高效实现优先队列。其基本性质如下：

结构性质：堆是一棵完全二叉树，可以用数组紧凑存储，无空洞。
- 对于数组下标从 0 开始的情况：
  - 节点i的父节点下标为(i-1)//2
  - 左孩子下标为2*i+1，右孩子为2*i+2
堆序性质：
- 大根堆（最大堆）：任意节点的值 ≥ 其左右子节点的值，根节点为最大值。
- 小根堆（最小堆）：任意节点的值 ≤ 其左右子节点的值，根节点为最小值。
建堆过程（自底向上调整）：
- 从最后一个非叶子节点开始，即第⌊n/2⌋ - 1个元素（0起始索引），向前依次调用HeapAdjust函数进行向下调整，直到根节点。
- 时间复杂度为 O(n)，优于逐个插入的 O(n log n)。
HeapAdjust（调整函数，以大根堆为例）：

defheap_adjust(data,s,m):# 在 data[s..m] 中，仅 data[s] 可能不满足堆性质，其余已满足temp=data[s]child=2*s+1# 左孩子whilechild<=m:# 找出较大的子节点ifchild<manddata[child]<data[child+1]:child+=1# 如果根不小于子节点，则已合适iftemp>=data[child]:break# 否则将较大子节点上移data[s]=data[child]s=child child=2*s+1data[s]=temp# 插入原 data[s] 到正确位置

HeapSort（堆排序算法）：

defheap_sort(data):n=len(data)# 构建大根堆：从最后一个非叶节点开始调整foriinrange(n//2-1,-1,-1):heap_adjust(data,i,n-1)# 逐个提取堆顶并重建堆foriinrange(n-1,0,-1):data[0],data[i]=data[i],data[0]# 堆顶与末尾交换heap_adjust(data,0,i-1)# 重新调整剩余元素成堆

性能分析：

时间复杂度：O(n log n) —— 建堆 O(n)，每次调整 O(log n)，共 n−1 次。
空间复杂度：O(1)，原地排序。
稳定性：不稳定，相同元素可能因父子交换而改变相对顺序。
适用场景：
- 数据量大且对最坏情况有要求（相比快排更稳定）；
- Top-K 问题（如找最大前 K 个数）；
- 实时系统中需要可预测性能的排序任务。
- 将一个数组原地构建成小根堆的过程与构建大根堆类似，核心思想是利用完全二叉树的结构特性和自底向上的调整策略。只需在调整函数中将比较方向反转（父节点 ≤ 子节点），即可实现小根堆。

步骤说明：

存储方式：使用数组表示完全二叉树，索引从 0 开始。
- 节点i的左孩子为2*i+1，右孩子为2*i+2
- 父节点为(i-1)//2
关键点：最后一个非叶子节点的下标是⌊n/2⌋ - 1（因为叶子节点没有子节点）。
调整顺序：从该节点开始，向前逐个调用min_heap_adjust函数进行“向下筛选”。

Python 实现代码

defmin_heap_adjust(data,s,m):""" 调整 data[s] 使得子树 data[s..m] 满足小根堆性质 前提：data[s] 的左右子树已经是小根堆 """temp=data[s]child=2*s+1# 左孩子whilechild<=m:# 选择较小的子节点ifchild<manddata[child]>data[child+1]:child+=1# 如果当前值已经不大于子节点，则位置合适iftemp<=data[child]:break# 否则将较小的子节点上移data[s]=data[child]s=child child=2*s+1data[s]=temp# 将原值放入正确位置defbuild_min_heap(data):""" 将数组 data 原地构建成小根堆 """n=len(data)# 从最后一个非叶子节点开始向前调整foriinrange(n//2-1,-1,-1):min_heap_adjust(data,i,n-1)# 示例使用arr=[4,10,3,5,1]build_min_heap(arr)print("小根堆:",arr)# 输出如: [1, 4, 3, 5, 10]