在最大堆中查找第二大元素的最快算法（具有重复项）

Question

如果你有一个包含 n 个整数的最大堆，那么找到第二大元素的最有效方法是什么？堆可以包含重复项，因此具有n-1最大值和1其他值的堆将返回另一个值

例如，包含数字的堆：

4,4,4,4,4,4,4,3,4

将返回值3。

有没有办法比O(n)运行时更快地做到这一点？

Answer 1

没有办法以比O(n)更好的时间复杂度来做到这一点。根据您提供的示例数据 ( 4,4,4,4,4,4,4,3,4)，堆可能是以下两者之一：

             4                      4
           /   \                  /   \
         4       4              4       4
        / \     / \            / \     / \
       4   4   4   4          4   4   3   4
      / \                    / \
     4   3                  4   4

... 3 可以位于任何叶节点中，因为这取决于插入顺序。当你从根开始遍历时，无法知道3是在左边还是在右边。

如果您愿意使用稍微替代的数据结构，那么可以在O(1)中完成：

在堆中存储唯一值。使用哈希图来存储有关您添加的值的信息。在简单的情况下，这个“信息”可以是一个发生计数器。因此，下次您想要在结构中插入相同的值时，您会检测到它已经在哈希图中，并且仅增加相应的出现计数器而不触及堆。

对于上面的例子，数据结构如下：

    heap              hashmap
                    key | value (=frequency)
       4           -----+-------------------
      /              4  |  8
     3               3  |  1

如果您的数据元素是由键与一些相关数据（属性）组合而成的复杂结构，那么您仍然只将键存储在堆中，而不会重复。然后，哈希映射不会为每个键提供计数器，而是提供共享同一键的实际数据元素的数组。

因此，需要明确的是，插入、删除和查找等操作的实现必须进行定制。这是一些伪代码，假设存在两个变量heap并且hashmap具有相应的行为：

             4                      4
           /   \                  /   \
         4       4              4       4
        / \     / \            / \     / \
       4   4   4   4          4   4   3   4
      / \                    / \
     4   3                  4   4

您可以获得小于最大值的最大值，如下所示：

key = max(heap.root.children())

...然后根据您期望的返回值，您还可以从哈希映射中获取相应的数据元素，甚至全部数据元素（当存在重复项时）。