给定最小堆H，给定时间复杂度的紧密O() [英] Given a minimum-heap H, give a tight O() bound on the time complexity

问题描述

我正在参加基础班250课，这是我提出的一个问题.没有人能够弄清楚这个问题.可能的答案在底部.给定最小堆H，在名为find3Min的方法的时间复杂度上给出一个紧密的O()，该方法查找但不删除H中的三个最小键.

Im taking a basic comp 250 class and this is a question I was given. No one has been able to figure this question out. The possible answers are at the bottom.Given a minimum-heap H, give a tight O() bound on the time complexity of a method called find3Min that finds, but does not remove, the three smallest keys in H .

假设该方法创建并返回三个最小元素的列表.要回答这个问题，您需要考虑如何实现这种方法.

Assume the method creates and returns a list of the three smallest elements. To answer this question you need to think of how such a method might be implemented.

1- O(n log(n))

1- O(n log(n))

2- O(log(n))

2- O(log(n))

3- O(3 log(n))

3- O(3 log(n))

4- O(1)

到目前为止，我倾向于4

as of now I'm leaning towards 4

推荐答案

下面的讨论假定二进制最小堆.将堆和其他非传统堆类型配对的解决方案大不相同.

The discussion below assumes a binary min heap. The solution for pairing heap and other non-traditional heap types is much different.

在最小堆中，两个最小的项是根项及其子项中的较小项.第三最小的是根的子代，或者第二最小的子代.考虑一下这两个堆:

In a min heap, the two smallest items are the root item and the smaller of its children. The third smallest is either a child of the root, or a child of the second smallest. Consider these two heaps:

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

在第一个中，第三个最小的是根的两个子中较大的一个.在第二个堆中，第三个项目是第二个最小项目的子项.无论您如何安排堆，第三项将是根的子项，或者是第二个最小的子项.

In the first, the third smallest is the larger of the root's two children. In the second heap, the third item is a child of the second smallest item. Regardless of how you arrange the heap, the third item will either be a child of the root, or a child of the second smallest.

因此，无论堆大小如何，您都可以在恒定时间内找到这三个项目.这使其变为O(1).

So you can find the three items in constant time, regardless of the size of the heap. That makes it 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

注意

以上讨论假定堆中的所有项目都是唯一的(或第二小"表示小于或等于最小").如果堆中可以有重复的项目，并且您想要第二个最小的唯一值，那么复杂度为O(n).

Note

The above discussion assumes that all items in the heap are unique (or that "second smallest" means "less than or equal to smallest"). If the heap can have duplicate items and you want the second smallest unique value, then the complexity is O(n).

这篇关于给定最小堆H，给定时间复杂度的紧密O()的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！