我正在阅读概率数据结构count min sketch如何用于查找数据流中的前k个元素。但我似乎无法理解我们保持一堆来获得最终答案的步骤。
问题：
我们有一个项目流
[B, C, A, B, C, A, C, A, A, ...]。我们被要求找出最频繁出现的前k项目。
我的理解是，这可以使用微批处理来完成，在微批处理中，我们在开始做一些真正的工作之前积累N个项目。
hashmap+heap方法对我来说很容易理解。我们遍历微批并通过计数元素来构建频率图(例如{B:34, D: 65, C: 9, A:84, ...}(。然后，我们通过遍历频率映射来维护大小为k的最小堆，根据需要添加到每个[item]:[freq]的堆中并从中移除。够直白的，没有什么花哨的。
现在有了CMS+heap，我们有了这个概率有损的2D数组，而不是哈希图，我们通过遍历微批来构建它。问题是：在给定这个CMS的情况下，我们如何保持最小堆大小为k
CMS只包含一组数字，而不包含原始项目。除非我也从微批中保留一组独特的元素，否则我无法知道最后需要针对哪些项目构建堆。但如果我这样做了，这难道不违背使用CMS节省内存空间的目的吗？
我还考虑过在遍历列表时实时构建堆。随着每个项目的到来，我们可以快速更新CMS，并获得该项目在该点的累积频率。但这个频率数字是累积的，这对我没有多大帮助。例如，对于上面的示例流，我们将得到[B:1, C:1, A:1, B:2, C:2, A:2, C:3, A:3, A:4, ...]。如果我们使用相同的逻辑来更新最小堆，我们会得到不正确的答案(重复(。
我肯定错过了什么。请帮我理解。
保留一个大小为k的哈希图，key是id，value是Item(id，count(使用Item保留大小为k的minheap随着事件的到来，更新count min 2d数组，获取min，更新hashmap中的Item，在堆中向上冒泡/向下冒泡以重新计算Item的顺序。如果堆大小>k、 poll min Item out并从hashmap以及中删除id
以下解释来自Youtube视频的评论：
我们需要存储密钥，但只有K个(或更多(。不是全部。当每一个密钥都到来时，我们会执行以下操作：
- 将其添加到计数最小草图中
- 从计数最小草图中获取密钥计数
- 检查当前密钥是否在堆中。如果它出现在堆中，我们会在那里更新它的计数值。如果它不在堆中，我们将检查堆是否已满。如果未满，我们将此键添加到堆中。如果堆已满，我们将检查最小堆元素，并将其值与当前键计数值进行比较。此时，我们可以移除最小元素并添加当前键(如果当前键计数>最小元素值(