什么是堆排序
堆排序是一种基于比较的排序算法，利用堆这种数据结构设计而成。堆本质上是一个完全二叉树，且满足父节点的值总是大于或小于子节点的值，前者叫大根堆，后者叫小根堆。堆排序就是通过不断构建和调整堆来完成元素排序的过程。
比如你有一堆考试成绩要从高到低排，用堆排序就像先把所有分数按规则摆成一个金字塔，每次把塔顶（最大值）拿走，剩下的再调整成新塔，重复操作直到全部排好。
堆的性质与存储方式
堆通常用数组来存储，不需要指针结构。对于下标从0开始的数组，如果某个节点在位置i，它的左孩子在2*i+1，右孩子在2*i+2，父节点在(i-1)/2。这种映射关系让堆的操作变得高效又简洁。
大根堆的关键特性是：每个节点都不小于它的左右孩子。因此堆顶元素一定是整个数组中的最大值，这正是堆排序能持续取出最大值的基础。
堆排序的核心步骤
整个过程分两步：建堆和排序。
第一步是将原始数组调整成一个大根堆。这个过程从最后一个非叶子节点开始，自右向左、自下而上地进行“下沉”操作，确保每个子树都满足堆的性质。
第二步是排序。将堆顶（最大值）与末尾元素交换，然后缩小堆的范围，对新的堆顶执行一次下沉，恢复堆的结构。重复这个过程，直到堆只剩一个元素。
代码实现示例
下面是用 Python 实现的堆排序代码：
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
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[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)这段代码先从中间位置倒序遍历，把数组变成大根堆。然后逐个把最大值移到末尾，并对剩余部分重新调整。最终得到一个升序排列的数组。
堆排序的特点
它的时间复杂度稳定在 O(n log n)，不管数据原本是什么样子，最坏和平均情况都一样。空间上只需要常数额外空间，属于原地排序算法。
不过它不是稳定的排序，相同值的相对位置可能在交换中被打乱。在实际开发中，像 Java 的优先队列底层就用了堆结构，理解堆排序对掌握这类工具很有帮助。
在处理大量数据、内存受限的场景下，堆排序比快排更可靠，不会因为数据分布差而性能骤降，适合嵌入式系统或底层模块使用。