关于霍尔堆排序的问题

Question

如果我没记错的话，

heapsort

的当前实现使用名为

treesort

的修改版本。我正在尝试理解 Williams 编写的原始算法。

OUTHEAP

被从未被调用过的

SWOPHEAP

调用。那么算法是如何工作的呢？用

min heap

替换

max heap

是该算法与每本书中的伪代码之间的唯一区别吗？

Answer 1

您表达了多个疑问/疑问，那么让我一一解答：

如果我没记错的话，堆排序的当前实现使用称为树排序的修改版本。

如果您阅读 Williams、Floyd 1963-1964 年的论文，您会得出以下结论。 Floyd 使用

TREESORT

这个名字来改进 Williams 发现的新奇事物，Williams 将数据结构称为堆，并将排序算法称为堆排序。此后，术语不断演变。

现在我们将考虑堆排序。弗洛伊德本质上是改进了威廉的

SETHEAP

函数，使其运行效率更高，但将他的函数称为

TREESORT 3

。今天，当我们提到树排序时，我们的意思是不同的：这是一种使用二叉搜索树作为数据结构的排序算法，它具有与二叉堆数据结构不同的属性。

OUTHEAP

被从未被调用过的

SWOPHEAP

调用。那么算法是如何工作的呢？

William 的目的并不是将

SWOPHEAP

用于他新颖的堆排序算法。他首先介绍了堆的概念（还不是排序算法），并提供了一些使用这样的堆的实用函数：

SETHEAP

、

INHEAP

、

OUTHEAP

和

SWOPHEAP

。

然后他写道：

这些过程可用于替换选择排序，用于对数组的元素进行排序，或用于选择不时添加新项目的任何项目集的当前最小值。

他并没有声称为了“所有”这些目的，必须使用“所有”这些实用函数。对于应用程序的最后一个示例，您将使用 SWOPHEAP，事实证明，您不需要它来实现堆排序。

用最大堆替换最小堆是该算法与每本书中的伪代码之间的唯一区别吗？

当然，并非“每本书”都以相同的方式介绍堆。有些人通过最小堆实现引入了这个概念，而另一些人则为此目的引入了最大堆。

最小堆可能更自然一些，因为堆可以被视为一种“部分排序”的集合，并且对于排序，我们还认为默认值是从最小到更大（按照惯例）。

但是要意识到，为了使用堆排序以非降序排序，您实际上需要一个最大堆！如果在堆排序中您将使用最小堆，您最终会得到一个从大到小的排序的列表。