给定最小堆 H，对时间复杂度给出严格的 O() 限制

Question

我参加了 250 基础课 class，这是我被问到的问题。没有人能够弄清楚这个问题。可能的答案在 bottom.Given 最小堆 H 中，对名为 find3Min 的方法的时间复杂度给出严格的 O() 限制，该方法查找但不删除 H 中的三个最小键。

假设该方法创建并 returns 一个包含三个最小元素的列表。要回答这个问题，您需要考虑如何实施这种方法。

1- O(n log(n))

2- O(log(n))

3- O(3 log(n))

4- O(1)

目前我倾向于 4

Answer 1

下面的讨论假设一个二进制最小堆。配对堆和其他 non-traditional 堆类型的解决方案有很大不同。

在最小堆中，两个最小的项目是根项目和它的 children 中较小的一个。第三小是根的 child，或者是第二小的 child。考虑这两个堆：

      A                   A
   B     C             B     D
  D E   F G           C G   F E

在第一、第三小的是根的两个children中较大的一个。在第二堆中，第三项是第二小项的child。无论您如何安排堆，第三项要么是根的 child，要么是第二小的 child。

所以无论堆的大小如何，你都可以在常数时间内找到这三个项目。这使得它 O(1).

伪代码：

s1 = root // smallest item
s2 = root.left
s3 = root.right
if (s2 > s3)
    swap(s2, s3)

// s2 now holds the second smallest item

// next smallest is either s3 (other child of root),
// or the smallest of s2's children
if (s3 > s2.left)
    s3 = s2.left
if (s3 > s2.right)
    s3 = s2.right

备注

上面的讨论假设堆中的所有项都是唯一的（或者说"second smallest"意味着"less than or equal to smallest"）。如果堆可以有重复项，而你想要第二小的唯一值，那么复杂度是 O(n)。

给定最小堆 H，对时间复杂度给出严格的 O() 限制

Given a minimum-heap H, give a tight O() bound on the time complexity

heap

methods

time-complexity

备注