异常教程

Python 堆排序（长文解析）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

在编程世界中，排序算法如同一把万能钥匙，能够解锁数据组织与效率优化的奥秘。堆排序（Heap Sort）作为经典的比较类排序算法之一，因其稳定的 O(n log n) 时间复杂度和无需额外空间的特点，在算法领域占据重要地位。本文将从零开始，通过生动的比喻和分步骤的代码实现，带您深入理解 Python 堆排序的核心原理，并探索其在实际场景中的应用价值。

1. 理解堆排序的基石：堆结构

堆排序的实现基于一种特殊的树形结构——堆（Heap）。堆是一种完全二叉树，其节点满足以下特性：

  • 最大堆（Max Heap）：每个父节点的值都大于或等于其子节点的值。
  • 最小堆（Min Heap）：每个父节点的值都小于或等于其子节点的值。

想象堆的结构如同一座金字塔：顶层的节点（根节点）是最大的（或最小的），向下逐层递减（或递增）。这种特性使得堆能够高效地找到最大值或最小值，成为排序算法的“秘密武器”。

堆的父子节点关系

在数组表示的堆中，节点的索引关系遵循以下规则：

  • 父节点索引：parent_index = (i - 1) // 2
  • 左子节点索引：left_child = 2 * i + 1
  • 右子节点索引：right_child = 2 * i + 2
父节点索引左子节点索引右子节点索引
012
134
256

2. 堆排序的核心步骤

堆排序的核心思想分为两部分：

  1. 构建初始堆：将原始数组转换为一个最大堆（或最小堆）。
  2. 调整堆结构：逐步将堆顶元素（最大值）与堆尾元素交换，并重新调整堆结构，最终完成排序。

2.1 构建最大堆

假设我们有一个数组 nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]，目标是将其转换为最大堆：

  1. 从最后一个非叶子节点开始：计算最后一个非叶子节点的索引为 (n//2 - 1)，其中 n 是数组长度。
  2. 向下调整（Heapify）：从当前节点出发，比较其与子节点的值，若父节点小于某个子节点，则交换两者的位置，并继续向下调整，直到堆的性质恢复。

示例代码片段（构建最大堆）：

def heapify(arr, n, i):  
    largest = i  
    left = 2 * i + 1  
    right = 2 * i + 2  

    if left < n and arr[i] < arr[left]:  
        largest = left  
    if right < n and arr[largest] < arr[right]:  
        largest = right  

    if largest != i:  
        arr[i], arr[largest] = arr[largest], arr[i]  
        heapify(arr, n, largest)

2.2 排序过程

构建好最大堆后，堆顶元素即为当前数组的最大值。通过以下步骤完成排序：

  1. 交换堆顶与堆尾：将最大值（堆顶）与堆尾元素交换，此时最大值被“冻结”到数组末尾。
  2. 缩小堆范围：将堆的大小减 1，排除已排序的元素。
  3. 重新调整堆：由于交换可能导致堆结构破坏，需对堆顶元素执行向下调整。
  4. 重复步骤 1-3，直到堆的大小为 1。

完整堆排序代码：

def heap_sort(arr):  
    n = len(arr)  

    # 构建最大堆  
    for i in range(n//2 - 1, -1, -1):  
        heapify(arr, n, i)  

    # 提取元素  
    for i in range(n-1, 0, -1):  
        arr[i], arr[0] = arr[0], arr[i]  # 交换  
        heapify(arr, i, 0)  # 调整堆（此时堆的大小为 i）  

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]  
heap_sort(arr)  
print("Sorted array:", arr)  # 输出：[1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

3. 堆排序的优化与变体

3.1 原地排序的优势

堆排序通过原地调整数组，无需额外空间存储中间结果，其空间复杂度为 O(1)，这在内存受限的场景中具有显著优势。

3.2 最小堆的排序应用

若希望从小到大排序，只需将最大堆替换为最小堆，调整 heapify 函数的比较逻辑即可。

3.3 时间复杂度分析

堆排序的最坏、平均、最好时间复杂度均为 O(n log n)。尽管其常数因子较大，但在数据规模较大时仍表现稳定。

4. 堆排序的实战案例

4.1 场景：实时数据流排序

假设需要从一个持续增长的数据流中，实时获取前 K 大的数值。此时，堆排序可结合最小堆实现高效筛选：

import heapq  

def top_k_numbers(stream, k):  
    min_heap = []  
    for num in stream:  
        heapq.heappush(min_heap, num)  
        if len(min_heap) > k:  
            heapq.heappop(min_heap)  
    return min_heap  # 返回前 K 大的元素  

stream = [10, 5, 8, 3, 12, 15, 7, 20]  
print("Top 3:", top_k_numbers(stream, 3))  # 输出：[12, 15, 20]

4.2 对比其他排序算法

堆排序与快速排序（Quick Sort）的对比：

  • 快速排序：平均性能更优（O(n log n)），但最坏时间复杂度为 O(n²)。
  • 堆排序：性能更稳定，适合数据规模较大或内存有限的场景。

5. 常见问题与调试技巧

Q1：为什么堆排序需要从非叶子节点开始调整？

A：叶子节点无需调整，因为它们没有子节点。从非叶子节点开始，确保调整后的父节点始终满足堆的性质。

Q2：堆排序的递归实现是否会栈溢出？

A：在极端情况下（如超大数组），递归可能导致栈溢出。此时可改用迭代方式实现 heapify 函数。

结论

堆排序凭借其稳定的性能和原地排序的特性，成为算法工具箱中的经典选择。通过本文的分步讲解和代码示例，您已掌握了 Python 堆排序 的核心逻辑，并能将其应用到实际问题中。无论是优化数据处理流程，还是应对算法面试中的排序挑战，堆排序都能为您提供可靠的支持。

后续探索建议：

  • 探究堆在优先队列（如 Dijkstra 算法）中的应用。
  • 尝试实现堆排序的并行化版本以提升性能。

通过持续实践与思考，您将逐渐掌握算法设计的底层逻辑，让编程之路更加游刃有余。

最新发布

查看更多文章