搜索最小二叉堆

Question

我需要用文字而非代码的方式简单地呈现一种算法，以查找最小二叉堆中的最大值。我的论点是，因为最小二叉堆在底部包含最高的值，所以如果你从索引的末尾开始搜索而不是从开头开始，你会立即找到它，而不是从开头搜索。这在实践和理论上都有意义吗？谢谢！

- user3555462

---

底部的含义是最高索引号。如果最小堆包含2在索引0处和100在索引30处。那么，如果您从索引30开始搜索，您将比从索引0开始快速找到该项。 - user3555462

Answer 1

以下是一个最小二叉堆：

        1
   2        5
3     4

仅仅是指出尽管最大值保证是一个叶子节点，但并不是所有的叶子节点都必须在树的最低层。

- user3386109

Answer 2

以下是一个最小二叉堆：

        1
    2       3
 10    5  20    7

“最大值”可以在叶子节点的任何位置。

如果您从索引末尾开始搜索，而不是从开头开始搜索，则会立即找到它，而不是从开头搜索。

那是不正确的。

跳过非叶子节点是可能的，但这并没有真正帮助渐进复杂度，因为具有n个元素的堆，大约有n/2个叶子节点。简单的线性扫描就可以了。

- Arun

Answer 3

二叉堆包含 ~n/2 个叶子节点，其中 n 是堆中元素的总数，而且其中一个将是最大值。

然而，您必须遍历所有这些元素才能找到最大值，因此您获得的加速只有 *2，并且使用此方法仍然是 O(n)。

- amit

Answer 4

二叉堆的结构是一棵平衡树。在内部，它可以被表示为节点树或数组。

如果它被表示为树，你只能遍历所有节点到叶子节点，这是一个O(n)的解决方案，除非你有对叶子节点的引用。

如果它被表示为数组，你可以做得更好。注意元素k的2个子节点分别在2k和2k+1处。这意味着你可以查看数组的末尾并向后遍历。这将更快，但仍然是O(n)。

- BrendanMcKee

Answer 5

如果堆的大小为n，则需要从索引n-1到(n-1)/2进行搜索。这些数字中最高的将给出最大值。

逐个搜索所有叶节点以找出最高数字。这是一个O(n/2)或O(n)操作。

- Biswajit_86

---

我相信范围是n-1到(n-1)/2。给定大小为n的基于数组的堆，如果2*p+1 >= n，则索引为p的节点是叶节点。解出p得到p = (n-1)/2。 - user3386109