堆排序 - 用树的力量实现最坏情况O(n log n)

📰 5W1H 发明者故事

Who（何人）- 发明者是谁？

发明者：J.W.J.威廉斯（J.W.J. Williams）
背景：威廉斯在1964年发表了堆排序，当时他在英国工作。他的论文简短（只有一页），却改变了排序算法的格局。同年，罗伯特·弗洛伊德（Robert W. Floyd，1978年图灵奖得主）发表了关于树选择排序的工作，并独立改进了堆的建立过程（Floyd’s heap construction, O(n)而非O(n log n)）。

当时的处境：1964年的排序世界：快速排序（1960年）已经存在，但其最坏情况O(n²)令人担忧。归并排序需要额外空间。研究者们希望找到一种原地、最坏情况O(n log n)的排序算法——威廉斯做到了。

When（何时）- 什么时候发明的？

时间：1964年（Williams发表），同年Floyd改进了建堆过程
时代背景：

• 计算机科学理论开始成熟，算法分析成为独立学科
• 实时系统需要有保证的最坏时间（而非平均时间）
• 1964年是算法史上重要一年：堆排序、B树前身、Floyd-Warshall都在这年附近诞生

Where（何地）- 在哪里发明的？

地点：英国计算机科学研究机构
环境：1960年代英国的计算机科学研究正在蓬勃发展，与美国形成了激烈的学术竞争。

What（何事）- 发明了什么？

算法：堆排序（Heapsort）
核心思想：

1. 建最大堆：将数组整理成最大堆（父节点总是大于子节点）
2. 逐步提取最大元素：将堆顶（最大值）与末尾交换，堆大小减1，重新维护堆性质

二叉堆的存储（0-indexed数组）：

父节点 i → 左子 2i+1，右子 2i+2
子节点 j → 父节点 (j-1)/2

关键突破：

• 最坏O(n log n)：不像快速排序有O(n²)的最坏情况
• 原地排序：只需O(log n)栈空间（维护堆时的调用栈）
• Floyd的O(n)建堆：从最后一个非叶节点向上sift-down，证明建堆是O(n)而非直觉上的O(n log n)

Why（何因）- 为什么发明？

问题：快速排序最坏O(n²)，归并排序需要O(n)额外空间。
目标：原地排序 + 最坏O(n log n) + 实现简单。
动机：利用优先队列（堆）的特性，可以高效获取最大元素，天然适合排序。

How（何果）- 如何实现？有什么影响？

时间复杂度：

• 建堆：O(n)（Floyd算法）
• 提取阶段：n次 × O(log n) = O(n log n)
• 总计：O(n log n)，所有情况均如此

历史影响：

• 操作系统优先级调度中的堆（priority queue）基于相同数据结构
• "堆"这个名字来自这篇论文（heap = 二叉堆）
• 在实践中比归并排序慢（缓存不友好），但保证最坏情况
• C++的 std::make_heap, std::push_heap, std::pop_heap 都基于堆排序原理

---

📝 自然语言需求定义

需求名称：实现堆排序，包含Floyd O(n)建堆优化

功能需求

1. sift_down：将以root为根的子树向下调整，恢复最大堆性质
2. build_heap：用Floyd算法O(n)建最大堆（从最后一个非叶节点倒序sift_down）
3. heapsort：建堆后逐步提取最大元素完成排序

验收标准

编号	测试场景	预期结果	验证方式
1	基本排序 [4,10,3,5,1]	[1,3,4,5,10]	逐元素比较
2	逆序数组 [9,8,…,1]	[1,2,…,9]	is_sorted
3	已排序数组	不变	is_sorted
4	含重复元素	正确排序	is_sorted
5	单元素数组	不变	直接检查
6	全相同元素	不变	is_sorted
7	1000个随机数	正确排序	is_sorted

---

💻 C语言实现文件

对应文件: heapsort.c

编译运行:

gcc -o heapsort_test heapsort.c
./heapsort_test

核心函数:

• sift_down(arr, n, root) - 维护堆性质
• build_heap(arr, n) - Floyd O(n)建堆
• heapsort(arr, n) - 堆排序