数组的BUILD-MAX-HEAP运行时间按降序排序 [英] BUILD-MAX-HEAP running time for array sorted in decreasing order

问题描述

我知道堆排序中BUILD-MAX-HEAP的运行时间为 O（n）。但是，如果我们有一个已经按降序排列的数组，为什么在BUILD-MAX-HEAP的运行时间内我们仍然有 O（n）？ >
是不是应该像 O（1）这样？它已经从最大值到最小值进行了排序，因此我们不需要MAX-HEAPIFY。

I know that the running time for BUILD-MAX-HEAP in heap sort is O(n). But, if we have an array that already sorted in a decreasing order, why do we still have O(n) for the running time of BUILD-MAX-HEAP?
Isn't it supposed to be something like O(1)? It's already sorted from the maximum value to the minimum value, so we do not need MAX-HEAPIFY.

我的理解正确吗？

推荐答案

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

You are right. It can of course be O(1). When you know for sure that your list is sorted you can use it as your max heap.

使用数组的堆的常见实现将以下行为用于其元素位置：

The common implementation of a heap using array uses this behavior for its elements position:

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

此规则适用于排序数组。 （降到最大堆，降到最小堆）。

This rule applies on a sorted array. (descending for max-heap, increasing for min-heap).

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

Please note that if you need to check first that the list is sorted it is of course still O(n).

编辑：堆排序复杂度

即使数组可能已排序并且构建堆实际上可能要花费 O（1）。每当您执行堆排序时，您仍将得到 O（n log n）。

如评论中所述，堆排序正在执行 n 调用 extract-max 。每个提取操作花费 O（log n）-我们最终得出的总时间复杂度为 O（n log n） 。

如果未对数组进行排序，我们将得到总时间复杂度为 O（n + nlogn），但仍为 O（n log n）。

Heap Sort Complexity
Even though the array might be sorted and building the heap might actually take O(1). Whenever you perform a Heap Sort you will still end up with O(n log n).
As said in the comments, Heap Sort is performing n calls to extract-max. Each extraction operation takes O(log n) - We end up with total time complexity of O(n log n).
In case the array is not sorted we will get total time-complexity of O(n + nlogn) which is still O(n log n).

这篇关于数组的BUILD-MAX-HEAP运行时间按降序排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！