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

Question

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

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

1. heapsort, without using `heap initialization' (i.e., by inserting the numbers repeatedly into an initially empty heap)

2. heapsort using heap initialization

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

我正在用 java 编写代码以供引用!

谢谢

Answer 1

区别在于您获取初始堆的方式。

https://en.wikipedia.org/wiki/Binary_heap (构建堆部分)。

William 的方法是将元素一个一个地插入到堆(最初为空)中。这个是 O(NlogN)。这个是未初始化的版本。

在 Floyd 的版本中，您获取数组并进行一些交换以使其成为堆。这将是 O(N)(查看维基百科的数学)。维基百科上提供的伪代码。

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