堆排序是什么？
你有没有遇到过这种情况：手头有一堆待办事项，但不知道先处理哪个。如果每次都能快速找到最紧急的那条，效率就会高很多。堆排序的逻辑就和这个类似——它利用“堆”这种数据结构，总能快速定位最大或最小的元素，然后依次整理整个序列。
堆排序是一种基于比较的排序算法，它把数组看成一个完全二叉树，并通过维护“大顶堆”或“小顶堆”的性质来完成排序。最终结果要么从小到大，要么从大到小，取决于你用哪种堆。
堆的结构特点
堆本质上是一个数组，只是我们把它想象成一棵完全二叉树。父节点和子节点之间有固定的下标关系：
- 父节点 i 的左孩子是 2*i+1
- 父节点 i 的右孩子是 2*i+2
- 任意节点 i 的父节点是 (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)这段代码里的 heapify 函数负责调整单个节点，让它及其子树满足大顶堆要求。heap_sort 先建堆，再不断把最大值移到末尾。
为什么选堆排序？
在实际应用中，堆排序的优势在于时间稳定。不管数据怎么分布，最坏、平均时间复杂度都是 O(n log n)，不像快排可能退化到 O(n²)。而且它原地排序，空间只用 O(1)，对内存紧张的环境挺友好。
比如你在路由器后台写了个日志分析模块，需要按时间戳排序几千条记录，又不想引入太多依赖，堆排序就是个可靠选择。虽然不如 Python 内置的 sorted() 快，但理解它能帮你更清楚底层发生了什么。
掌握堆排序不只是为了写排序函数，更重要的是理解“堆”这种结构在任务调度、优先队列等场景中的广泛应用。下次看到“优先处理紧急任务”，不妨想想是不是可以用堆来实现。