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

Question

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

Answer 1

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

    5
  4   1
 3 2

最小的项永远不会有子项，所以它必须要么在堆的底行，要么在下一行。