时间戳

首页 > 解决方案 > 在最大堆中找到第二大元素的最快算法（有重复项）

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

问题描述

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

例如，包含数字的堆：

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

将返回值3。

有没有比运行时更快的方法O(n)？

标签： algorithmdata-structuresheap

解决方案

没有比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)中完成：

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

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

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

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

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

function insert(element):
    key = element.key
    if key not in hashmap:
        hashmap.set(key, new Array)
        heap.insert(key)
    arr = hashmap.get(key) # get a reference to the array
    arr.append(element) # add element to array, affecting the hashmap-stored value

function extract(): # remove max element
    if heap.size() == 0:
        return # No more data
    key = heap.peek() # look at root value
    arr = hashmap.get(key) # get a reference to the array
    element = arr.pop() # extract from array, affecting the hashmap-stored value
    if arr.length() == 0:
        heap.extract()
        hashmap.delete(key)
    return element

function peek(): # return element with max value
    if heap.size() == 0:
        return # No more data
    key = heap.peek() # look at root value
    arr = hashmap.get(key)
    element = arr[-1] # last element in array
    return element

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

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

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

推荐阅读