基础堆排序（手把手讲解）

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

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 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+ 小伙伴加入学习 ，欢迎点击围观

前言

在算法学习的旅程中，排序算法是绕不开的核心内容。从简单的冒泡排序到高效的快速排序，每种算法都有其独特的应用场景和性能特点。今天，我们将聚焦于一种兼具实用性和理论深度的排序算法——基础堆排序。它通过巧妙的堆结构设计，能够在 O(n log n) 的时间复杂度内完成排序任务，尤其适合处理大规模数据场景。本文将从零开始讲解堆排序的底层逻辑、实现步骤，并通过代码示例和实际案例帮助读者掌握这一算法。

核心概念解析

什么是堆？

堆（Heap）是一种特殊的完全二叉树结构，它满足以下两个条件之一：

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

可以将堆想象成一个“金字塔家族”：顶端的父辈永远是家族中的“最大值”或“最小值”，而子辈则按照层级依次排列。这种结构使得堆在获取最大值或最小值时，仅需 O(1) 的时间复杂度。

堆的存储方式

堆通常使用数组进行存储，其索引关系遵循以下规则：

• 父节点的索引为 i，则左子节点的索引为 2*i + 1，右子节点的索引为 2*i + 2。
• 反之，子节点的父节点索引为 (i-1)//2。

例如，数组 [10, 5, 8, 3, 2] 对应的最大堆结构如图：

      10  
    /    \  
   5      8  
  / \  
 3   2  

通过索引计算，父节点 10（索引 0）的左子节点是索引 1（值为 5），右子节点是索引 2（值为 8）。

堆排序的核心步骤

步骤 1：构建初始堆

堆排序的第一步是将原始数组构建成一个最大堆（或最小堆）。以最大堆为例，我们需要通过“下沉操作”（Sift Down）调整数组元素，确保每个父节点的值都不小于子节点。

下沉操作的比喻

想象堆是一个“权力金字塔”，父节点必须比子节点更“强大”。若某个父节点的值小于子节点，就需要让父节点“下放权力”给子节点，直到整个结构恢复平衡。

具体实现

1. 从最后一个非叶子节点（即索引 (n-2)//2）开始向前遍历，逐个执行下沉操作。
2. 对每个节点，比较其与子节点的值，若不符合最大堆条件，则交换值更大的子节点与父节点的位置。

步骤 2：排序过程

构建好最大堆后，堆顶元素（索引 0）即为当前数组的最大值。我们将该最大值与数组末尾元素交换，缩小待排序区域的范围，然后重新调整堆结构，重复这一过程直至排序完成。

具体步骤分解

1. 交换元素：将堆顶元素（最大值）与当前未排序区域的最后一个元素交换。
2. 缩小范围：将未排序区域的边界前移一位。
3. 重新调整堆：对缩小后的堆区域执行下沉操作，确保剩余元素仍满足最大堆的条件。

图解过程

假设初始数组为 [4, 10, 3, 5, 1]，构建最大堆后变为 [10, 5, 3, 4, 1]。

• 第一次交换后：[1, 5, 3, 4, 10]，未排序区域为前 4 个元素。
• 调整堆后：[5, 4, 3, 1, 10]，继续交换得到最终排序结果 [1, 3, 4, 5, 10]。

堆排序的代码实现

Python 代码示例

以下是一个完整的堆排序实现，包含构建堆和排序的核心逻辑：

def heap_sort(arr):
    n = len(arr)
    
    # 构建最大堆
    for i in range(n//2 - 1, -1, -1):
        sift_down(arr, n, i)
    
    # 排序过程
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换堆顶与末尾元素
        sift_down(arr, i, 0)  # 重新调整堆（排除已排序的末尾元素）
        
def sift_down(arr, n, root):
    largest = root  # 初始化最大值为父节点
    left = 2 * root + 1
    right = 2 * root + 2
    
    # 比较左子节点
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 比较右子节点
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # 若父节点不是最大值，交换并递归调整子树
    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        sift_down(arr, n, largest)

代码解析

1. 构建最大堆：通过 sift_down 函数从最后一个非叶子节点开始下沉调整。
2. 排序循环：每次交换堆顶元素到末尾后，堆的有效范围缩小，需再次调整堆结构。
3. 时间复杂度：构建堆的时间为 O(n)，排序循环中每个元素的下沉操作为 O(log n)，总时间复杂度为 O(n log n)。

优化与注意事项

1. 原地排序：堆排序直接在原数组上操作，空间复杂度为 O(1)。
2. 不稳定排序：堆排序不保证相等元素的相对顺序，因此不适合需要稳定性的场景。
3. 性能对比：相比快速排序的平均 O(n log n)，堆排序的最坏情况性能更稳定（均为 O(n log n)），但常数因子稍大。

实际案例分析

案例 1：排序整数数组

假设输入数组为 [7, 3, 5, 8, 2, 9, 1]，堆排序过程如下：

1. 构建最大堆：通过下沉调整，最终堆结构为 [9, 8, 7, 3, 2, 5, 1]。
2. 排序阶段：
   • 第一次交换后：[1, 8, 7, 3, 2, 5, 9]，调整堆后变为 [8, 5, 7, 3, 2, 1, 9]。
   • 第二次交换后：[1, 5, 7, 3, 2, 8, 9]，调整堆后得到 [7, 5, 1, 3, 2, 8, 9]。
   • 最终排序结果：[1, 2, 3, 5, 7, 8, 9]。

案例 2：处理大规模数据

假设有一个包含 100 万个随机数的数组，堆排序的性能表现如何？

• 优势：由于其 O(n log n) 的时间复杂度，即使数据量庞大，也能在合理时间内完成排序。
• 对比：与快速排序相比，堆排序在最坏情况下（如已排序数组）表现更稳定，而快速排序可能退化到 O(n²)。

常见问题与解答

Q1：堆排序的“下沉操作”如何避免无限循环？

A1：在 sift_down 函数中，当父节点已经是当前子树的最大值时（即 largest == root），函数停止递归，因此不会无限循环。

Q2：能否用最小堆实现堆排序？

A2：可以！只需将最大堆的比较条件反转（即父节点小于等于子节点），最终排序结果会是逆序。只需在交换元素时调整逻辑即可。

Q3：堆排序的适用场景有哪些？

A3：

• 需要稳定时间复杂度的场景（如实时系统）。
• 内存有限时的原地排序需求。
• 需要频繁获取最大值/最小值的场景（如优先队列）。

结论

堆排序凭借其简洁的逻辑和稳定的性能，在算法世界中占据重要地位。通过理解堆的结构特性、掌握下沉操作的细节，以及结合代码实现的实践，开发者可以轻松应对各类排序需求。无论是处理数据量庞大的日志文件，还是优化实时系统的排序逻辑，堆排序都是一个值得深入学习的工具。

希望本文能帮助读者建立起对基础堆排序的全面认知，并在实际项目中灵活应用这一算法。通过持续练习与思考，算法学习的挑战终将成为解决问题的钥匙。