构建堆的时间复杂度

使用 heapify 操作构建堆的时间复杂度取决于我们使用的方法；让我们了解一下我们有哪些方法。

构建堆有两种标准方法

朴素方法（插入）

在此方法中，我们必须单独将每个元素插入到堆中。

从一个空堆开始，我们逐个插入元素。

由于您插入了 n 个元素，使用此方法构建堆的总时间复杂度为 O(n log n)。

Floyd 算法（Heapify）

Floyd 算法是构建堆的一种更有效的方法。

它以自底向上的方式工作，从最后一个非叶节点开始并对每个节点进行堆化。

堆化单个节点的时间复杂度为 O(log n)，其中 n 是堆中的元素数量。

由于堆中存在 n/2 个非叶节点，使用 Floyd 算法构建堆的总时间复杂度为 O(n)。

在实践中，Floyd 算法因其更好的时间复杂度而成为构建堆的首选方法，使其比朴素插入方法更有效。Floyd 算法的 O(n) 项涉及的常数因子通常小于插入方法的 O(n log n) 项涉及的常数因子。

让我们来实现这两种方法的代码。

让我们来实现朴素方法的代码。

代码

输出

说明

heapify 函数

接受一个堆和一个索引作为参数。将给定索引处的元素向上移动，直到满足堆属性。

buildHeapInsertion 函数

它从第二个元素开始遍历数组。对每个元素调用 heapify，有效地将其插入堆中。

main 函数

它使用值初始化一个数组。调用 buildHeapInsertion 使用插入方法构建堆。打印生成的堆。

时间复杂度

提供的使用插入方法的堆构建的时间复杂度为 O(n log n)，其中 n 是数组中的元素数量。

另一种方法：Heapify

输出

说明

heapify 函数

接受一个堆、堆的大小 (n) 和一个索引作为参数。

将给定索引处的元素与其左子节点和右子节点进行比较，并在需要时与较大的子节点交换。

递归地调用 heapify 对被交换的子节点索引。

buildHeapFloyd 函数：从最后一个非叶节点迭代到堆的根节点。

对每个节点调用 heapify，有效地将数组转换为堆。

main 函数

使用值初始化一个数组。

调用 buildHeapFloyd 使用 Floyd 算法构建堆。打印生成的堆。

时间复杂度

提供的使用 Floyd 算法（也称为 heapify 或自底向上堆构建）的堆构建的时间复杂度为 O(n)，其中 n 是数组中的元素数量。

两种方法最终都会得到一个有效的堆。第一种方法（朴素插入）逐个将元素插入堆中，而第二种方法（Floyd 算法）使用自底向上的方法高效地构建堆。