图解堆排序：从零开始手把手教你两种建堆方法（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 ≈ nlogn3. 自底向上建堆法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 选择策略建议数据规模敏感型当n10⁶时优先选择自底向上内存受限环境两种方法空间复杂度均为O(1)代码简洁需求自顶向下实现更直观易懂5. 堆排序完整实现结合两种建堆方式的完整示例def heap_sort(arr, methodbottom-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