java - 堆初始化是什么意思？

Question

我正在为一个数据结构类做一个编码作业。我基本上必须实现不同的排序算法（选择排序、快速排序等）并比较运行时间。

但是，在指令中，它说我必须实现两种不同的堆排序算法。这是说明：

1. 堆排序，不使用“堆初始化”（即，通过将数字重复插入到最初为空的堆中）

2. 使用堆初始化进行堆排序

在这里，我不确定堆初始化是什么意思。我试图用谷歌搜索它，但我找不到任何可以很好解释的来源。实现带/不带堆初始化的堆排序是什么意思？

我正在用java编码以供参考！

谢谢

标签： javaalgorithmsorting

Answer 1

不同之处在于您如何获得初始堆。

https://en.wikipedia.org/wiki/Binary_heap（构建堆部分）。

有威廉的方法，您将元素一个一个地插入堆中（最初是空的）。这个是 O(NlogN)。这是未初始化的版本。

在 Floyd 的版本中，您可以使用数组并进行一些交换以使其成为堆。这个将是 O(N) （检查维基百科的数学）。伪代码可在维基百科上找到。

总体而言，复杂性是由 O(NlogN) 的提取过程驱动的。