堆排序算法详解与实现

排序算法：堆排序（HeapSort）

**关键定义：**二叉堆，不稳定的选择排序算法

**定义：**堆排序标准定义

堆排序（Heap Sort）是基于二叉堆数据结构实现的一种原地、不稳定的选择排序算法，其核心是利用堆'父节点与子节点间的大小约束特性'，通过构建初始堆和反复提取堆顶极值 + 重新堆化的操作，将无序序列逐步转换为有序序列。

一、前置知识点

1. 二叉堆

堆是一个完全二叉树，主要存在两种类型：

大顶堆：每个父节点的值 ≥ 其左右子节点的值，堆顶（根节点）是整个堆的最大值。

小顶堆：每个父节点的值 ≤ 其左右子节点的值，堆顶是整个堆的最小值。

注：采用大顶堆则堆排序为升序，采用小顶堆为降序。

2. 链表和数组这两种线性存储结构

堆排序中对于元素的储存大多采用数组结构，原因如下：

特性	数组	链表（单链表）
存储结构	连续内存空间	非连续节点 + 指针串联
访问方式	随机访问（O(1)）	顺序访问（O(n)）
插入 / 删除（中间）	O(n)（需移动元素）	O(1)（仅改指针，找前驱 O(n)）
长度特性	静态固定（动态数组需扩容）	动态可变
内存开销	仅存数据，开销小	数据 + 指针，额外开销大
缓存友好性	优（连续预加载）	差（分散无预加载）
内存分配要求	需连续大空间，要求高	小块分散空间，要求低
代码实现复杂度	简单	较高（需处理指针）

结构先天适配：堆是完全二叉树，节点排列有规律，能和数组的连续索引一一对应，通过简单公式即可定位父/子节点，这是数组成为堆最优存储结构的根本原因；

效率完美匹配：数组的 O(1) 节点定位、缓存友好、原地存储特性，让堆排序的核心操作（堆化、构建堆、堆顶交换）保持高效，确保堆排序 O(n log n) 的时间复杂度和 O(1) 的空间复杂度；

短板完全规避，优势充分发挥：数组的通用缺点（连续内存、静态长度）在堆排序的固定数据量、无动态增删场景下可忽略，而链表的核心优点（动态增删、内存灵活）在堆排序中无意义，核心短板（定位慢、开销大、缓存差）却会直接让堆排序的效率大幅下降，甚至丧失算法优势。

二、堆排序实现过程（数组实现）

假设有如下二叉树

步骤 1：确定堆化的起始节点（最后一个非叶子节点）

构建初始大顶堆时，无需对叶子节点执行堆化（叶子节点无左右子节点，本身已满足堆性质），只需从开始，依次对每个节点执行「向下堆化」操作。