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

Question

我需要在一个流中存储前k个最频繁的元素。为了估计频率，我使用count-min-sketch算法。我的流是由键(字符串)组成的。因此，基本上每次我在我的流中遇到新的密钥时，我都会通过查看count-min-sketch数据结构来计算到目前为止当前密钥的频率。但是，我无法存储前k个最频繁的密钥。

我的第一个想法是将它们存储在一个大小固定为k的最小堆中，然后在这个最小堆中存储频率，键与比较器比较频率。因此，每当我得到一个键的频率时，我会尝试查看堆大小是否超过k，如果是，则将当前键的频率与min-heap中的最高(最小)频率进行比较，如果当前键的频率较高，则弹出顶部，并将键插入到堆中。

然而，我意识到min-heap不是一个集合，这意味着它允许复制。假设我有一个非常热的键，我一直在流中计数它，所以每次我将这个频率，键插入堆中，最终我的堆将充满相同的键，只有不同的频率。

所以我想知道有没有一个好方法来存储count-min-sketch中的前k个不同的更频繁的元素。

Answer 1

您还可以维护所有三种数据结构1. Count-min sketch来存储您在流中遇到的所有内容2.最小大小为k的堆3.大小为k的散列映射

在热门项的情况下-您增加计数并从count-min sketch获得新的频率，假设该项已经存在于min-heap中，您从hash-map获得该项并增加频率

当你遇到一个不同的项目，它的频率刚刚增加，并且进入了著名的min-heap，你可以同时从min-heap和hash-map中取出根，所以基本上min-heap可以帮助你维护前k个频繁的项目，并使用hash-map来随机访问那些频繁的项目。请注意，min-heap和hash-map都可以映射到相同的内存地址，因此只能对存储在hash-map中的项执行更新频率

Answer 2

维护堆中已有的[key,<frequency,position>]对的哈希图是有意义的。position指堆中键的索引(假设基于数组的堆)。当密钥到达时，您检查两个条件：

-the密钥在哈希表中

-its频率已更改

如果两者都为真，那么您将在O(1)时间内找到堆中的键，因为您已经在hashmap中存储了它的位置，然后修改键的频率，并根据频率的增加或降低，从该位置(O(logn))执行冒泡下降或冒泡上升。更改位置后，使用新的频率和位置值更新该键的hashmap条目。

如果from one为false，则按照通常的逻辑，即将键与根进行比较，如果堆已满并且键的频率大于根的频率，则将根从堆中弹出并将其从hashmap中删除，同时将键插入堆和hashmap。

如果key在hashmap中，但是它的频率没有改变，那么您什么也不做。