algorithm - 从不断更新的列表中获取最大数量

Question

几天前，我在一次系统设计面试中遇到了这个问题。我省略了无关的部分，专注于问题的核心部分。它是这样的。

假设我们有一组 k,v 对，键是字符串，值是整数。我们可以假设有一组固定的键（例如 k1、k2、...、kn）。有一些代理将这些 k,v 对连续推送到系统中，就像流一样。我们需要做的就是将当前值添加到所有传入对的旧值中。

让我们举个例子。在 time t0，假设我们有以下 kv 对。

k1: 100
k3: 200

在 time t1，有两个传入对。k2: 50, k3: 150. 所以，在t1，系统的状态是：

k1: 100
k2: 50
k3: 350

目标是在周期性间隔内给出具有最大值的密钥。我想不出任何算法，它可以提供比 max-heapify 更好的运行时间。我想建立一个最大堆，然后在每个新数据到来时更新它。对于每次更新，heapify()将花费最大log(n)时间。在每次调用时，我们都可以返回堆的根。但是还有比这个更好的解决方案吗？

标签： algorithmheap

Answer 1

这取决于（1）所有更新是否都是单调的（2）取决于您的计算模型。

如果值只增加（单调更新），那么显然您可以在恒定时间内保持内存中迄今为止存在的所有值的最大值。

否则，如果这些值是小整数，那么您可以使用Y-fast trie将运行时间提高到最大值O(log log M)所在的位置。M

如果只允许比较，那Theta(log n)是你能做的最好的，因为这种结构可以自适应地用于排序，并且排序n元素需要O(n log n)比较。给定一个未排序的数组，将每个元素插入到不同的键下。查询最大值，将其键设置为负无穷大（或小于最小值元素的某个值），然后重复以降序读取元素。