在最大堆中找到最小元素的最佳算法是什么

Question

在最大堆中查找最小元素的最佳算法(就时间复杂性而言(是什么？

Answer 1

最大堆中的最小元素保证在最后(n/2+1(个项中，其中n是堆中的项数。因此，找到它的最佳方法是对最后n/2个项目进行顺序扫描。例如，考虑一个包含5个项目的堆：

5
4   1
3 2

最小的项永远不会有子项，所以它必须在堆的最下面一行，或者在上一行。