存储来自 count-min-sketch 的前 k 个结果

Question

我需要在流中存储前 k 个最频繁的元素。为了估计频率，我使用 count-min-sketch 算法。我的流由键（作为字符串）组成。所以基本上每次我在我的流中遇到一个新键时，我都会通过查看 count-min-sketch 数据结构来计算到目前为止当前键的频率。但是我无法存储前 k 个最常用的键。我的第一个想法是将它们存储在一个固定大小为 k 的最小堆中。我将 [频率，键] 存储在这个最小堆中，并使用比较器比较频率。因此，每次我获得一个键的频率时，我都会尝试查看堆大小是否超过 k，如果是，那么我将当前键的频率与最小堆中的最高（最小）频率进行比较，如果我当前的键是频率较大然后我弹出顶部，并将我的密钥插入堆中。但是我意识到最小堆不是一个集合，这意味着它允许重复。假设我有一个非常热的键，并且我一直在流中计算它，所以每次我将这个 [频率，键] 插入堆中时，最终我的堆将充满相同的键，只是频率不同。所以我想知道有没有一种好方法可以在 count-min-sketch 中存储前 k 个不同的更频繁的元素。

Answer 1

您还可以维护所有三个数据结构 1. Count-min 草图以存储您在流中遇到的所有内容 2. 大小为 k 的最小堆 3. 大小为 k 的哈希图

如果是热门项目 - 您增加计数并从 count-min 草图中获取新频率，假设此项目已存在于 min-heap 中，则您从哈希映射中获取该项目并增加频率

当您遇到一个频率刚刚增加并进入著名的最小堆的不同项目时，您可以同时从最小堆和哈希映射中驱逐根，因此基本上最小堆可以帮助您维护前 k 个频繁项目和哈希-map 随机访问那些频繁项目。请注意，min-heap 和 hash-map 都可以映射到相同的内存地址，因此更新频率只能对存储在 hash-map 中的项目进行

Answer 2

维护[key,<frequency,position>]堆中已经存在的对的哈希图是有意义的。position指的是堆内键的索引（假设是基于数组的堆）。当键到达时，您检查 2 个条件：
- 键在哈希图中
- 它的频率已经改变

如果两者都为真，你会O(1)及时在堆中找到键，因为你已经将它的位置存储在哈希图中，然后修改键的频率，并根据频率是增加还是减少，你从那个位置（O(logn)）。更改位置后，您可以使用新的频率和位置值更新该键的哈希图条目。

如果第一个为假，则遵循通常的逻辑，即将键与根进行比较，如果堆已满且键的频率大于根的频率，则将根从堆中弹出并将其从哈希图中删除，同时插入进入堆和哈希映射的键。

如果键在哈希图中但它的频率没有改变，你什么都不做。