当所有元素都相同时，堆排序的运行时间
我们可以说，当大小为 n 的数组 A 中所有元素都相同时，堆排序的运行时间为 O(n)
-->如果是这种情况，堆排序的最佳情况运行时间是否为 O(n)
Can we say that, when all elements are identical in an array A of size n then running time of heap sort is O(n)
--> If this is the case, Is O(n) best case running time of heapsort
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
当所有元素都相等时，构建堆需要 O(n) 步骤。因为当元素在一次比较 O(1) 后添加到堆时，我们看到它位于正确的位置。
移除根也是O(1)，当我们交换尾部和根时，堆性质仍然满足。
所有元素都在 O(n) 内添加到堆中，并在 O(n) 内删除。所以，是的，在这种情况下，堆排序的复杂度是 O(n)。我想不出更好的情况，所以堆排序最好的情况必须是 O(n)。
“堆排序最好的情况是 O(n)”在英语中的意思是：存在大小为 n 的数组，使得堆排序最多需要 k*n 比较才能对其进行排序。这在理论上很好，但在实践中它并没有说明堆排序有多好或多快。
When all elements are equal building the heap takes O(n) steps. Because when element gets added to the heap after one compare O(1) we see it is in the correct position.
Removing the root is also O(1), when we swap the tail and root, the heap property is still satisfied.
All elements get added to the heap in O(n), and removed in O(n). So, yes in this case heapsort is O(n). I can't think of a better case so heapsorts best case must be O(n).
'Heapsorts best case is O(n)' means in English something like: there exists arrays of size n such that heapsort needs at most k*n compares to sort it. That's nice in theory but in practice it doesn't say much about how good or fast heapsort is.