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

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

1. 结构性质：堆是一棵完全二叉树，可以用数组紧凑存储，无空洞。

   • 对于数组下标从 0 开始的情况：
     • 节点i的父节点下标为(i-1)//2
     • 左孩子下标为2*i+1，右孩子为2*i+2

2. 堆序性质：

   • 大根堆（最大堆）：任意节点的值 ≥ 其左右子节点的值，根节点为最大值。
   • 小根堆（最小堆）：任意节点的值 ≤ 其左右子节点的值，根节点为最小值。

3. 建堆过程（自底向上调整）：

   • 从最后一个非叶子节点开始，即第⌊n/2⌋ - 1个元素（0起始索引），向前依次调用HeapAdjust函数进行向下调整，直到根节点。
   • 时间复杂度为 O(n)，优于逐个插入的 O(n log n)。

4. 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] 到正确位置

5. 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)# 重新调整剩余元素成堆

6. 性能分析：

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

步骤说明：

1. 存储方式：使用数组表示完全二叉树，索引从 0 开始。

   • 节点i的左孩子为2*i+1，右孩子为2*i+2
   • 父节点为(i-1)//2

2. 关键点：最后一个非叶子节点的下标是⌊n/2⌋ - 1（因为叶子节点没有子节点）。

3. 调整顺序：从该节点开始，向前逐个调用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]

特点分析

• 时间复杂度：O(n)，虽然单次调整为 O(log n)，但由于树的层次分布特性，整体建堆为线性。
• 空间复杂度：O(1)，原地操作。
• 稳定性：堆排序本身不稳定，但建堆过程不影响稳定性讨论（排序时才体现）。

通过上述方法，可以高效地将任意数组原地转换为一个小根堆，适用于最小优先队列、Top-K 最小元素等问题。