堆排序（Heap Sort）是一种基于堆数据结构的排序算法。堆是一种特殊的树形数据结构，通常是一个完全二叉树，满足堆序性质：对于最大堆，父节点的值总是大于或等于其子节点的值；对于最小堆，父节点的值总是小于或等于其子节点的值。堆排序的基本思想是先将待排序的序列构造成一个大顶堆（或小顶堆），然后将堆顶元素（即当前最大值或最小值）与末尾元素交换，再将剩余元素重新调整为堆，如此反复，直至整个序列有序。
以下是堆排序的基本步骤：
构建堆：将待排序的序列调整为一个大顶堆（或小顶堆）。通常从最后一个非叶子节点开始（即最后一个节点的父节点），自下而上、从右到左进行调整，确保每个节点及其子节点满足堆序性质。
交换堆顶元素与末尾元素：将堆顶元素（即当前最大值或最小值）与末尾元素交换，此时末尾元素已处于正确位置，而原来的堆顶元素成为新的末尾元素。
调整堆：将剩余元素（除去已排序的末尾元素）重新调整为堆。由于堆的性质被破坏，需要从新堆顶（原次大值或次小值）开始向下调整，直至整个堆满足堆序性质。
重复步骤2和3：继续交换堆顶元素与新的末尾元素，然后调整堆，直至整个序列有序。
时间复杂度：
- 最好情况、最坏情况、平均情况：无论输入数组的原始顺序如何，堆排序的时间复杂度均为 O(nlogn)。这是因为构建堆的过程需要O(n) 时间，而交换堆顶元素与末尾元素并调整堆的过程需要重复 n−1 次，每次调整堆的时间复杂度为 O(logn)。
空间复杂度：堆排序是原地排序算法，只需要常数级别的额外空间用于临时存储交换的元素，因此空间复杂度为 O(1)。
稳定性：堆排序不是稳定的排序算法，因为相同的元素可能会因为堆调整过程中的位置交换而改变排序后的相对顺序。
堆排序结合了堆数据结构的优点，能够在原地完成排序，且时间复杂度稳定为 O(nlogn)，适用于对大规模数据进行排序。以下是堆排序的Python实现：
Python
1def heapify(arr, n, i):
2 largest = i # 初始化最大值索引为当前节点
3 left = 2 * i + 1 # 左子节点索引
4 right = 2 * i + 2 # 右子节点索引
5
6 if left < n and arr[largest] < arr[left]: # 如果左子节点存在且大于父节点
7 largest = left
8
9 if right < n and arr[largest] < arr[right]: # 如果右子节点存在且大于父节点
10 largest = right
11
12 if largest != i: # 如果最大值不在当前节点
13 arr[i], arr[largest] = arr[largest], arr[i] # 交换当前节点与最大值节点的值
14 heapify(arr, n, largest) # 递归调整子树
15
16
17def heap_sort(arr):
18 n = len(arr)
19
20 # 构建大顶堆
21 for i in range(n, -1, -1): # 从最后一个非叶子节点开始向上调整
22 heapify(arr, n, i)
23
24 # 交换堆顶元素与末尾元素，调整堆，直至整个序列有序
25 for i in range(n-1, 0, -1):
26 arr[i], arr[0] = arr[0], arr[i] # 交换堆顶元素与末尾元素
27 heapify(arr, i, 0) # 调整剩余元素为堆
28
29 return arr首先通过heapify函数自下而上、从右到左调整待排序序列，使其满足大顶堆的性质。然后通过交换堆顶元素与末尾元素，并调用heapify函数重新调整剩余元素为堆，直至整个序列有序。
