在Min堆中寻找第7个最小元素

Question

在min-heap中，在根处有最小元素的n个元素中，在时间上可以找到第7个最小的元素-

a) Θ(nlogn)
b) Θ(n)
c) Θ(logn)
d) Θ(1)

==========================================================================

我很困惑于选项c和d。我们是否需要提取Min 7 times，还是简单地进行根级-0比较，根与LC和RC之间的1级-3比较，等等。

Answer 1

我想说这个问题是模棱两可。

如果我们必须使用堆接口，我们只能提取最少6次，并查看第7次最小值。每一次，除了最后一次，我们可以花费任何地方，从1 (最好的情况)到log n (最坏的情况)操作，所以它是O(log n)，而不是Theta的任何东西。第7次手术为Theta(1).

--如果我们能够利用堆的内部结构(正如Yves Daoust已经指出的那样)，我们可以确保堆在其前7个级别中包含它的最小元素，这些级别最多包含1+2+4+8+16+32+64=127元素。在存储堆的数组的前127个数字中找到最小值是Theta(1)，因为不管大小如何，127仍然是一个常量，不依赖于n。

考虑到这个选项(c)在第一种情况下并不是一个正确的答案(如果使用O()而不是Theta())，我将使用(d)。

Answer 2

在最坏的情况下，第7个元素将出现在堆的第7个级别中，其中最多包含127个元素。您可以通过对这些元素进行排序来找到它，这需要O(1)。

警告:这不是一个有效的过程，这是一个简单的理论论证，证明这个问题可以在恒定的时间内解决。

一个可能更好的过程是在127元素堆上执行堆排序的选择阶段，这将在更糟的情况下进行，比如lg 127 + lg 126 + lg 125 + lg 124 + lg 123 + lg 122 + lg 121操作(非常粗略的估计，但没关系，这是O(1))。

Answer 3

在min中，堆元素不像二进制搜索树那样存储(即左侧小于根，右侧更大)。一个较小的元素可以出现在任何子节点上，因此，我们不能像在二进制搜索树中那样搜索元素。

因此，我们需要首先从堆中弹出前6个元素并将它们存储在数组中，现在第7个元素位于根节点上，所以我们弹出并存储它。现在，我们将前面弹出的所有6个元素都推到堆中。

时间复杂度：-7次手术到pop，6次手术推送，因此总共7+6= 13次手术。每次操作都需要花费大量的时间。因此，时间复杂度变成13*logn或简单的O(logn)。