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.
Is my understanding correct? Could someone please explain it to me?
你说的对。当然可以O(1)。当您确定您的列表已排序时，您可以将其用作最大堆。
使用数组的堆的常见实现将这种行为用于其元素位置：
childs[i] = 2i+1 and 2i+2
parent[i] = floor((i-1)/2)
此规则适用于排序数组。（max-heap 递减，min-heap 递增）。
请注意，如果您需要首先检查列表是否已排序，它当然仍然是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).
如果您知道该数组已按降序排序，则无需对其进行排序。如果您希望它按升序排列，您可以在 O(n) 时间内反转数组。
如果您不知道数组是否已经排序，则需要 O(n) 来确定它是否已经反向排序。
从反向排序数组构建最大堆被认为是 O(n) 的原因是您必须从项目 n/2 开始，并且向后工作，确保元素不小于其子元素。即使只有 n/2 次检查，它也被认为是 O(n)，因为执行的操作数与要检查的项目总数成正比。
顺便说一句，有趣的是，您可以从一个反向排序的数组中构建一个最大堆，这比检查该数组是否是反向排序的要快。