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

Question

在最大堆中找到最小元素的最佳算法是什么（就时间复杂度而言）？

Answer 1

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

    5
  4   1
 3 2

最小的项永远不会有子项，因此它必须在堆的底行或上一行。