堆初始化意味着什么？

Question

我正在为数据结构类做一个编码分配.我基本上必须实现不同的排序算法(Selection Sort,QuickSort等)并比较运行时间.

但是,在指令上,它说我必须实现两种不同的堆排序算法.这是指令:

1. heapsort,不使用`堆初始化'(即通过将数字重复插入最初的空堆)

2. 使用堆初始化的heapsort

在这里,我不确定堆初始化是什么意思.我试图谷歌它,但我找不到任何可以解释的来源.通过/不使用堆初始化实现堆排序是什么意思？

我在java中编码以供参考!

谢谢

Answer 1

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

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

有William的方法,您可以将元素逐个插入堆中(最初为空).这个是O(NlogN).这是未初始化的版本.

这是Floyd的版本,您可以使用数组并进行一些交换以使其成为堆.这个将是O(N)(检查维基百科的数学).维基百科上有伪代码.

总体而言,复杂性由提取过程驱动,即O(NlogN).