我可以用 O(lgn) 时间找到具有最小堆的第二大元素吗？
Can I find the second largest element with a min heap with O(lgn) time?
我的看法：
在最小堆中，最大的元素总是在叶子上。叶子的数量在lg(n+1)/2和lg(n+1)之间。通过在叶子之间进行线性搜索，我总能在 O(lgn) 时间内找到堆中最大的元素。删除该项目会花费常数时间。线性搜索叶子可以在 O(lgn) 时间内为我们提供堆中第二大元素。
但是，麻省理工学院的教授说我们不能那样做。
Quiz solution in MIT 6.006
我想知道我的解决方案有什么问题。
二叉树的最大节点数是
其中有 2^k 张叶子。所以基本上几乎所有叶子的一半 O(n)，这甚至不接近你的对数估计。你的算法将 运行 最有可能在 O(n log n)
我的看法： 在最小堆中，最大的元素总是在叶子上。叶子的数量在lg(n+1)/2和lg(n+1)之间。通过在叶子之间进行线性搜索，我总能在 O(lgn) 时间内找到堆中最大的元素。删除该项目会花费常数时间。线性搜索叶子可以在 O(lgn) 时间内为我们提供堆中第二大元素。
但是，麻省理工学院的教授说我们不能那样做。 Quiz solution in MIT 6.006
我想知道我的解决方案有什么问题。
二叉树的最大节点数是
其中有 2^k 张叶子。所以基本上几乎所有叶子的一半 O(n)，这甚至不接近你的对数估计。你的算法将 运行 最有可能在 O(n log n)