algorithm - 从二进制最大堆中删除第二个最小的元素

Question

这个问题类似于this .区别在于我有一个二进制最大堆而不是最小堆。这使得问题完全不同。

我的想法:

1) 我遍历所有节点以找到第二小的元素，这将花费 O(n)

2) 当我找到第二个最小的元素时，我将那个元素向上冒泡，通过将它与它的父元素交换直到它到达根，这将花费 O(logn)

3) 我从根中删除元素并取出最右边的元素并将其存储在根位置(常规堆删除操作)，这将花费 O(logn)

总计为 O(n) + O(logn) + O(logn)，也就是 O(n)。

已编辑:添加了二进制

还有比这更好的解决方案吗？

Answer 1

为什么不保留一个包含 2 个元素的小数组来保留最小的 2 个元素的副本？

然后，所有操作仅需 O(1) 步更改，您可以在恒定时间内提供答案。