我需要在流中存储前 k 个最常见的元素。为了估计频率，我使用 count-min-sketch 算法。我的流由键（作为字符串）组成。所以基本上每次我在我的流中遇到一个新键时，我都会通过查看 count-min-sketch 数据结构来计算当前键的频率。但是我无法存储前 k 个最常用的键。
我的第一个想法是将它们存储在一个固定大小为 k 的最小堆中。我用比较器比较频率将 [频率，键] 存储在这个最小堆内。所以每次我得到一个密钥的频率时，我都会尝试查看堆大小是否超过 k，如果是，那么我将当前密钥的频率与最小堆中的顶部（最小）频率进行比较，如果我当前的密钥是频率大于我弹出顶部，然后将我的密钥插入堆中。
但是我意识到最小堆不是一个集合，这意味着它允许重复。假设我有一个非常热的键，并且我一直在流中对其进行计数，所以每次我将此 [频率，键] 插入堆时，最终我的堆将充满相同的键，只是频率不同。
所以我想知道是否有一种好方法可以将前 k 个不同的更频繁的元素存储在 count-min-sketch 中。
您还可以维护所有三个数据结构 1. Count-min sketch 以存储您在流中遇到的所有内容 2. 大小为 k 的最小堆 3. 大小为 k 的哈希图
如果是热项目 - 您增加计数并从 count-min 草图中获取新频率，假设该项目已经存在于 min-heap 中，您从哈希映射中获取项目并增加频率
当您遇到频率刚刚增加并进入著名的最小堆的不同项目时，您可以同时从最小堆和哈希映射中逐出根，因此基本上最小堆可以帮助您维护最高 k 频率的项目和哈希-map 随机访问那些频繁的项目。请注意，min-heap 和 hash-map 都可以映射到相同的内存地址，因此更新频率只能对存储在 hash-map 中的项目进行
[key,<frequency,position>]维护堆中已经存在的对的哈希图是有意义的。position指堆内键的索引（假设基于数组的堆）。当密钥到达时，您检查 2 个条件：
- 密钥在 hashmap 中
- 它的频率发生了变化
如果两者都为真，您会O(1)及时在堆中找到键，因为您已经将其位置存储在哈希图中，然后修改键的频率，并根据频率是增加还是减少，您可以进行向下冒泡或向上冒泡那个位置 ( O(logn))。更改位置后，您使用新的频率和位置值更新该键的哈希图条目。
如果第一个是假的，你遵循通常的逻辑，即比较 key 和 root，如果堆已满并且 key 的频率大于 root 的频率，那么你将 root 从堆中弹出并从 hashmap 中删除，同时插入堆和hashmap的键。
如果 key 在 hashmap 中但它的频率没有改变，你什么都不做。