图解堆排序：从零开始手把手教你两种建堆方法（Python代码示例）
图解堆排序：从零开始手把手教你两种建堆方法（Python代码示例）
堆排序作为经典排序算法之一，其核心在于如何高效构建堆结构。本文将用图解+代码的方式，带你彻底理解两种主流建堆方法——自顶向下（插入式）与自底向上（Floyd式）的实现差异。无论你是准备技术面试还是夯实算法基础，掌握这些建堆技巧都能让你在数据处理时游刃有余。
1. 堆结构基础认知
1.1 堆的本质特性
堆是一种特殊的完全二叉树，具有以下核心特征：
- 大顶堆性质：任意节点的值≥其子节点值（根节点为最大值）
- 小顶堆性质：任意节点的值≤其子节点值（根节点为最小值）
实际存储时通常采用数组实现，利用完全二叉树的特性建立索引映射：
# 索引关系公式 parent = (i - 1) // 2 # 父节点索引 left_child = 2 * i + 1 # 左子节点索引 right_child = 2 * i + 2 # 右子节点索引1.2 堆排序的基本流程
完整堆排序分为两个阶段：
- 建堆阶段：将无序数组调整为堆结构
- 排序阶段：反复取出堆顶元素并调整结构
关键提示：建堆方式直接影响算法整体性能，不同场景下可选用自顶向下或自底向上方法
2. 自顶向下建堆法
2.1 算法原理图解
自顶向下建堆如同"插卡游戏"，从第二个元素开始逐个插入并调整：
初始数组: [3,1,4] 步骤1: [3] → 插入1 → [3,1] (无需调整) 步骤2: 插入4 → [3,1,4] → 4与父节点3比较 → 交换 → [4,1,3]2.2 Python实现细节
核心操作是sift_up上浮函数：
def sift_up(arr, i): while i > 0 and arr[(i-1)//2] < arr[i]: # 大顶堆比较 arr[(i-1)//2], arr[i] = arr[i], arr[(i-1)//2] i = (i - 1) // 2 return arr def build_heap_top_down(arr): for i in range(1, len(arr)): # 从第二个元素开始 sift_up(arr, i) return arr2.3 时间复杂度分析
建堆过程的时间复杂度为O(nlogn)，主要消耗在：
- 第k个元素插入时最多需要⌈log₂k⌉次比较
- 所有元素插入的总比较次数约为∑logk ≈ nlogn
3. 自底向上建堆法
3.1 Floyd算法精要
从最后一个非叶子节点开始逆向调整：
示例数组: [3,1,4,5,2] 非叶子节点索引: len(arr)//2 - 1 = 1 调整顺序: 节点1 → 节点03.2 代码实现技巧
关键sift_down下沉函数：
def sift_down(arr, i, size): largest = i l, r = 2*i + 1, 2*i + 2 if l < size and arr[l] > arr[largest]: largest = l if r < size and arr[r] > arr[largest]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] sift_down(arr, largest, size) def build_heap_bottom_up(arr): for i in range(len(arr)//2 -1, -1, -1): # 逆向遍历非叶节点 sift_down(arr, i, len(arr)) return arr3.4 性能优势解析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 建堆过程 | O(n) | 数学推导证明总和收敛于n |
| 整体排序 | O(nlogn) | 与自顶向下法最终复杂度相同但常数项更优 |
4. 两种方法实战对比
4.1 核心差异点
调整方向：
- 自顶向下：子节点与父节点比较（上浮）
- 自底向上：父节点与子节点比较（下沉）
适用场景：
- 动态数据：自顶向下适合流式数据插入
- 静态数据：自底向上适合已知全部数据的批量处理
4.2 选择策略建议
- 数据规模敏感型：当n>10⁶时优先选择自底向上
- 内存受限环境：两种方法空间复杂度均为O(1)
- 代码简洁需求：自顶向下实现更直观易懂
5. 堆排序完整实现
结合两种建堆方式的完整示例：
def heap_sort(arr, method='bottom-up'): if method == 'bottom-up': arr = build_heap_bottom_up(arr) else: arr = build_heap_top_down(arr) # 排序阶段 for i in range(len(arr)-1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # 交换首尾 sift_down(arr, 0, i) # 调整剩余堆 return arr实际测试对比：
import time data = [random.randint(0,10000) for _ in range(100000)] start = time.time() heap_sort(data, 'top-down') print(f"自顶向下耗时: {time.time()-start:.4f}s") start = time.time() heap_sort(data, 'bottom-up') print(f"自底向上耗时: {time.time()-start:.4f}s")输出结果示例：
自顶向下耗时: 0.3827s 自底向上耗时: 0.2914s