在最小堆中找到第 7 个最小的元素
Finding the 7th smallest element in Min heap
在n个元素的min-heap中，最小的元素在根部，可以及时找到第7小的元素-
a) Θ(nlogn)
b) Θ(n)
c) Θ(logn)
d) Θ(1)
============================================= =============================
我对选项 c 和 d 感到很困惑。我们是否需要进行提取 Min 7 times 或简单地在根级别进行比较 - 0 比较，在第一级别 - 根与 LC 和 RC 之间的 3 比较等等。
在最小堆中，元素不像二叉搜索树那样存储（即左侧小于根，右侧大于根）。较小的元素可以出现在任何子节点，因此我们不能像在二叉搜索树中那样搜索元素。
因此，我们需要先从堆中弹出前 6 个元素并将它们存储在数组中，现在第 7 个元素在根节点上，因此我们将其弹出并存储。现在我们将之前弹出的所有 6 个元素推入堆中。
时间复杂度：- 7 次弹出操作和 6 次推送操作，因此总共有 7 + 6 = 13 次操作。并且每个操作都花费 logn 时间。
因此，时间复杂度变为 13*logn 或简单的 O(logn)
在最坏的情况下，第 7 个元素 会在堆的前 7 层找到，其中最多包含 127 个元素。您可以通过对这些元素进行排序来找到它，这需要 O(1).
注意：这并不是一个有效的过程，它只是一个简单的理论论证，用于证明问题可以在常数时间内解决。
一个可能更好的过程是在 127 个元素的堆上执行堆排序的选择阶段，这将采取更糟糕的 lg 127 + lg 126 + lg 125 + lg 124 + lg 123 + lg 122 + lg 121 操作（很粗略的估计，不过没关系，是O(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).
答案将是 O(n)。这里的每个人都假设您将有一个常量范围，在该范围内您可以找到答案，因此 O(1) 将是答案，但他们错过了最小堆的一点可以有重复项。假设第 6 个最小的元素有 100 万个重复项，那么当它甚至没有给出重复项的数量时，你将如何计算范围，最重要的是，假设最后一个元素是第 7 个最小的元素，你将不得不搜索整个数组。因此答案是n.
在n个元素的min-heap中，最小的元素在根部，可以及时找到第7小的元素-
a) Θ(nlogn)
b) Θ(n)
c) Θ(logn)
d) Θ(1)
============================================= =============================
我对选项 c 和 d 感到很困惑。我们是否需要进行提取 Min 7 times 或简单地在根级别进行比较 - 0 比较，在第一级别 - 根与 LC 和 RC 之间的 3 比较等等。
在最小堆中，元素不像二叉搜索树那样存储（即左侧小于根，右侧大于根）。较小的元素可以出现在任何子节点，因此我们不能像在二叉搜索树中那样搜索元素。
因此，我们需要先从堆中弹出前 6 个元素并将它们存储在数组中，现在第 7 个元素在根节点上，因此我们将其弹出并存储。现在我们将之前弹出的所有 6 个元素推入堆中。
时间复杂度：- 7 次弹出操作和 6 次推送操作，因此总共有 7 + 6 = 13 次操作。并且每个操作都花费 logn 时间。 因此，时间复杂度变为 13*logn 或简单的 O(logn)
在最坏的情况下，第 7 个元素 会在堆的前 7 层找到，其中最多包含 127 个元素。您可以通过对这些元素进行排序来找到它，这需要 O(1).
注意：这并不是一个有效的过程，它只是一个简单的理论论证，用于证明问题可以在常数时间内解决。
一个可能更好的过程是在 127 个元素的堆上执行堆排序的选择阶段，这将采取更糟糕的 lg 127 + lg 126 + lg 125 + lg 124 + lg 123 + lg 122 + lg 121 操作（很粗略的估计，不过没关系，是O(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).
答案将是 O(n)。这里的每个人都假设您将有一个常量范围，在该范围内您可以找到答案，因此 O(1) 将是答案，但他们错过了最小堆的一点可以有重复项。假设第 6 个最小的元素有 100 万个重复项，那么当它甚至没有给出重复项的数量时，你将如何计算范围，最重要的是，假设最后一个元素是第 7 个最小的元素，你将不得不搜索整个数组。因此答案是n.