堆排序的空间复杂度为 O(1)，是因为它是一种 原地排序（in-place sorting）算法 —— 也就是说，除了输入数组本身，它只需要常数级别的额外存储空间（如几个变量用于索引、临时交换等），而不需要与输入规模 n 成比例的额外内存。

下面我们从原理和实现两个角度详细解释：

✅ 一、什么是“空间复杂度”？

• 空间复杂度衡量的是 算法在运行过程中所需的额外存储空间（不包括输入数据本身）。
• 如果一个算法只用到固定数量的变量（比如 i, j, temp），不管输入多大，这些变量的数量不变，那么它的空间复杂度就是 O(1)。

✅ 二、堆排序为什么是 O(1)？

1. 堆结构直接用原数组表示

• 堆是一棵完全二叉树，可以用数组紧凑地表示：
  • 根节点在 arr[0]
  • 节点 i 的左孩子在 2i + 1，右孩子在 2i + 2
  • 父节点在 (i-1)//2
• 因此，不需要新建树结构或指针，直接在原数组上操作即可。

2. 建堆和排序都在原数组上进行

• 建堆阶段：从最后一个非叶子节点开始，自底向上调用 sift_down，所有操作都是原地交换元素。
• 排序阶段：
  • 将堆顶（最大值）与当前堆的最后一个元素交换
  • 缩小“堆的有效范围”（用一个变量 end 表示）
  • 对新堆顶执行 sift_down
• 整个过程只用了几个辅助变量（如 i, child, temp），没有递归调用栈（如果用迭代实现 sift_down）。

📌 注意：如果 sift_down 用递归实现，最坏情况下递归深度为 O(log n)，此时空间复杂度会变成 O(log n)（因为函数调用栈）。
但标准堆排序通常采用迭代版 sift_down，从而保证 真正的 O(1) 空间复杂度。

✅ 三、对比其他排序算法
排序算法 空间复杂度 是否原地
堆排序 O(1) ✅ 是
快速排序 O(log n) ~ O(n) ✅（但递归栈占用空间）
归并排序 O(n) ❌ 否（需要临时数组）
冒泡/插入/选择排序 O(1) ✅ 是

所以堆排序在时间稳定（O(n log n)）+ 空间高效（O(1)） 方面非常有优势。

✅ 四、代码佐证（迭代版 sift_down）

def heapsort(arr):
n = len(arr)

# 建堆（O(n)）
for i in range(n // 2 - 1, -1, -1):
    sift_down(arr, i, n - 1)

# 排序（O(n log n)）
for end in range(n - 1, 0, -1):
    arr[0], arr[end] = arr[end], arr[0]
    sift_down(arr, 0, end - 1)

def sift_down(arr, start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 = arr[child]:
break
arr[root], arr[child] = arr[child], arr[root]
root = child # 迭代，无递归！

✅ 这段代码中：

• 没有创建新数组
• 没有递归
• 只用了 root, child 等几个局部变量 → O(1) 额外空间

✅ 总结

堆排序的空间复杂度是 O(1)，因为它：

1. 直接在原数组上构建和调整堆；
2. 使用迭代方式实现下沉操作，避免递归栈；
3. 仅使用常数个辅助变量，不依赖输入规模 n。

这使得堆排序特别适合内存受限的环境（如嵌入式系统、大规模数据处理），也是它被广泛使用的重要原因之一。

如果你看到某些资料说堆排序空间复杂度是 O(log n)，那很可能是假设了递归实现。但在理论分析和实际工程中，标准堆排序默认指迭代实现，空间复杂度为 O(1)。