当所有元素都相同时，堆排序的运行时间

Question

我们是否可以说，当大小为n的数组A中所有元素都相同时，堆排序的运行时间为O(n)

->如果是这种情况，堆排序的最佳运行时间是O(n)

Answer 1

当所有元素相等时，构建堆需要O(n)步。因为当一个元素在一次比较0(1)之后被添加到堆中时，我们看到它在正确的位置。

移除根也是O(1)，当我们交换尾部和根时，堆属性仍然满足。

所有元素在O(n)内被添加到堆中，并在O(n)内被移除。所以，在这个情况下堆排序是O(n)我想不出更好的情况，所以堆排序的最佳情况一定是O(n)。

'堆排序的最佳情况是O(n)'在英语中意思是:存在大小为n的数组，使得堆排序最多需要k*n个数组来排序。这在理论上很好，但在实践中它并不能说明堆排序有多好或多快。