关于Williams原始Heapsort算法的若干技术疑问

1. SWOPHEAP与OUTHEAP的调用逻辑 #

Williams在1964年提出的原始堆排序算法中，SWOPHEAP并非未被调用——它是OUTHEAP函数的内部辅助子过程，仅在OUTHEAP执行堆结构调整时被触发，不会被外部逻辑直接调用。

具体运作流程：

• 排序阶段会循环调用OUTHEAP，每次提取最小堆的堆顶元素（当前未排序区间的最小值）；
• OUTHEAP执行时，先将堆顶元素与堆的最后一个元素交换，随后调用SWOPHEAP将新堆顶元素向下调整，重新维护最小堆的性质。

你观察到的“SWOPHEAP未被直接调用”，只是因为它是OUTHEAP的内部依赖，算法的外层逻辑只需调用OUTHEAP就能完成堆顶提取和堆重构操作。

2. 原始算法与现代教材伪代码的差异 #

将最小堆替换为最大堆只是差异之一，还有两个核心区别：

• 堆构建方式：Williams的原始算法采用**逐个插入元素+上滤（sift up）的方式建堆，时间复杂度为O(n log n)；而现代多数教材伪代码使用Floyd提出的从中间节点开始下滤（sift down）**方法，建堆时间复杂度优化为O(n)。
• 元素处理逻辑：原始算法基于最小堆，每次取出的最小值会被放到数组末尾，最终生成升序数组；现代基于最大堆的实现则是将每次取出的最大值放到末尾，同样得到升序数组——虽然结果一致，但堆类型和元素移动的细节逻辑完全不同。

内容的提问来源于stack exchange，提问作者Nocxy