0

这个问题与此类似。不同之处在于我有一个二进制 Max-Heap而不是Min-Heap。这使得问题完全不同。

我的想法：

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

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

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

总计将是 O(n) + O(logn) + O(logn)，即 O(n)。

编辑：添加二进制

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

4

3 回答 3

1

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

然后，所有操作都只用 O(1) 步骤改变，您可以在恒定时间内提供答案。

于 2012-07-10T12:33:47.950 回答
0

The second smallest element is either a leaf or parent of a leaf and the leaf is the only child of it.

How to remove the second smallest element:

  1. Find it by searching through leaves and possibly the father that has only one child. O(n)
  2. If the 2nd smallest element is parent of a node, the node must be the smallest element and should be the right most leaf. Replace the 2nd smallest with its child and it is over. O(1)
    If the 2nd smallest element is a leaf, replace it with the right most leaf in the deepest level and bubble up. O(log(n))

So it is O(n)+O(log(n)) which is still O(n) but with fewer comparisons.

于 2012-05-09T15:32:49.350 回答
0

When it comes to big O notation - no, it cannot be done better. Finding an arbitrary element in a max heap is O(n).

You could however reduce the number of maximum nodes you need to traverse to 1/2 * n, and essentially double the speed of the algorithm. [still O(n) domain], since the 2nd smallest element in a max heap has at most one son, so you can traverse only leaves (n/2 of those), and one element at most which has only one son. (remember, a binary heap is an array representing a complete tree, thus at most one element has exactly one son).

One can also enhance a bit the removal step, but I doubt it will have any significant affect), so I wouldn't bother putting effort into it.

于 2012-05-09T15:35:02.840 回答