这个问题类似于this .区别在于我有一个二进制最大堆而不是最小堆。这使得问题完全不同。
我的想法:
1) 我遍历所有节点以找到第二小的元素,这将花费 O(n)
2) 当我找到第二个最小的元素时,我将那个元素向上冒泡,通过将它与它的父元素交换直到它到达根,这将花费 O(logn)
3) 我从根中删除元素并取出最右边的元素并将其存储在根位置(常规堆删除操作),这将花费 O(logn)
总计为 O(n) + O(logn) + O(logn),也就是 O(n)。
已编辑:添加了二进制
还有比这更好的解决方案吗?
最佳答案
为什么不保留一个包含 2 个元素的小数组来保留最小的 2 个元素的副本?
然后,所有操作仅需 O(1) 步更改,您可以在恒定时间内提供答案。
关于algorithm - 从二进制最大堆中删除第二个最小的元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10518985/