按降序排序的数组的BUILD-MAX-HEAP运行时间
我知道堆排序中BUILD-MAX-HEAP的运行时间是O（n）。但是，如果我们有一个已经按降序排序的数组，为什么对于BUILD-MAX-HEAP的运行时间仍然有O（n）<它不是应该是类似于O（1）的吗？它已经从最大值到最小值排序，因此我们不需要MAX-HEAPIFY。
我的理解正确吗？谁能给我解释一下吗？
共有2个答案
如果您知道数组已经按降序排序，则无需对其进行排序。如果您希望它按升序排列，您可以在O（n）时间内反转数组。
如果您不知道数组是否已经排序，则需要O（n）来确定它是否已经反向排序。
从反向排序数组构建最大堆被认为是O（n）的原因是，您必须从第n/2项开始，并向后操作，确保元素不小于其子元素。即使只有n/2个检查，也被认为是O（n），因为执行的操作数与要检查的项目总数成比例。
顺便说一句，有趣的是，您可以从反向排序的数组构建最大堆，而不是检查数组以查看它是否反向排序。
你是对的。它当然可以是O（1）。当您确定列表已排序时，可以将其用作最大堆。
使用数组的堆的常见实现对其元素位置使用此行为：
childs[i] = 2i+1 and 2i+2
parent[i] = floor((i-1)/2)
此规则适用于排序数组。（最大堆递减，最小堆递增）。
请注意，如果您需要首先检查列表是否已排序，它当然仍然是O（n）。
编辑：堆排序复杂度，即使可能对数组进行排序，并且构建堆实际上可能需要0（1）。无论何时执行堆排序，最终结果仍然是O（n log n）
如注释中所述，堆排序正在执行对提取最大值的调用。每个提取操作需要0（log n）-我们最终得到的总时间复杂度为0（log n）<如果数组没有排序，我们将得到总时间复杂度为O（n nlogn），它仍然是O（n log n）。
-
我正在开发一个程序，通过将数组划分为较小的最大堆并从每个堆中提取最大整数，然后将其从堆中删除并再次运行，直到每个堆都为空，来对数组进行排序，但我似乎无法理解。 从我的立场来看，代码看起来不错，但我没有得到我想要的结果。我的输入是随机创建的，并生成512个整数的数组。下面是它为一个示例运行打印的内容- 有人能发现我的代码有什么问题吗？我会非常高兴的。 （1） 主程序 （2） 最大堆类 （3）输入创建
-
问题内容： 以下代码将按 升序 对数组进行排序： 我需要 按降序 排序。如何使用比较器执行此操作？ 请帮忙。 问题答案： 对于原始数组类型，您必须编写一个反向排序算法： 或者，您可以将转换为并编写比较器： 或使用，因为它仅适用于非原始数组类型。 最后，
-
有人能提供帮助，如何检查排序降序数组以及？干杯！
-
我很惊讶以前没有人问过这个特定的问题，但我真的没有在SO上或。 假设我有一个包含整数的随机numpy数组，例如： 但我希望解决方案按降序排序。 现在，我知道我总能做到： 但这最后一句话是否高效？它不创建一个按升序排列的副本，然后反转这个副本以得到按反转顺序排列的结果吗？如果情况确实如此，是否有一个有效的替代方案？看起来不像接受参数来更改排序操作中比较的符号，以获得相反的顺序。
-
问题内容： 我有一个很大的原始类型数组（double）。如何按降序排列元素？ 不幸的是，Java API不支持使用比较器对原始类型进行排序。 可能想到的第一种方法是将其转换为对象列表（装箱）： 但是，对数组中的每个原语进行装箱速度太慢，并且会导致很大的GC压力！ 另一种方法是排序然后反转： 这种方法也很慢 -特别是在数组已经很好排序的情况下。 有什么更好的选择？ 问题答案： Java Primit
-
问题内容： 有没有什么简便的方法可以按降序对数组进行排序，就像它们在Arrays类中如何按升序排序？ 问题答案： 你可以使用它对所有对象进行排序 不能直接用于降序对原始数组进行排序。如果尝试Arrays.sort()通过传递由定义的反向 来调用该方法，则会抛出错误 找不到适合sort（int []，comparator）的方法 可以与“对象数组”（例如整数数组）一起使用，但不能与基本数组（例如整数