我们可以说，当大小为 n 的数组 A 中的所有元素都相同时，堆排序的运行时间是 O(n)
-->如果是这样的话，是不是O(n)个堆排序的最佳情况运行时间
最佳答案
当所有元素都相等时，构建堆需要 O(n) 步。因为当元素在一次比较 O(1) 后被添加到堆中时，我们看到它位于正确的位置。
移除根也是O(1)，当我们交换尾和根时，堆性质仍然满足。
所有元素在 O(n) 中添加到堆中，并在 O(n) 中移除。所以，是的，在这种情况下堆排序是 O(n)。我想不出更好的情况，所以堆排序的最佳情况必须是 O(n)。
“Heapsorts best case is O(n)”在英语中的意思是这样的:存在大小为 n 的数组，因此 heapsort 最多需要 k*n 比较才能对其进行排序。这在理论上很好，但在实践中并没有说明堆排序有多好或多快。
关于algorithm - 堆排序的运行时间，当所有元素都相同时，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8164445/