algorithm - BUILD-MAX-HEAP 运行时间，用于按降序排列的数组

Question

我知道堆排序中 BUILD-MAX-HEAP 的运行时间是O(n)。但是，如果我们有一个已经按降序排序的数组，为什么 BUILD-MAX-HEAP 的运行时间仍然是 O(n)？
它不应该是类似O(1) 的东西吗？它已经从最大值到最小值排序，所以我们不需要 MAX-HEAPIFY。

我的理解对吗？有人可以给我解释一下吗？

Answer 1

你是对的。它当然可以是O(1)。当您确定您的列表已排序时，您可以将其用作最大堆。

使用数组的堆的常见实现对其元素位置使用此行为:

childs[i] = 2i+1 and 2i+2
parent[i] = floor((i-1)/2)

此规则适用于排序数组。 (最大堆递减，最小堆递增)。

请注意，如果您需要先检查列表是否已排序，它当然仍然是O(n)。

编辑:堆排序复杂度
即使数组可能已排序并且构建堆实际上可能需要 O(1)。每当您执行堆排序时，您仍将以 O(n log n) 结束。
如评论中所述，堆排序正在对 extract-max 执行 n 调用。每个提取操作都需要 O(log n) - 我们最终的总时间复杂度为 O(n log n)。
如果数组未排序，我们将得到 O(n + nlogn) 的总时间复杂度，它仍然是 O(n log n)。