系统设计：数据流中出现最频繁的k个元素(find top k frequent items in a data stream) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

系统设计：数据流中出现最频繁的k个元素(find top k frequent items in a data stream)

系统设计：数据流中出现最频繁的k个元素(find top k frequent items in a data stream)# JobHunting - 待字闺中

P*e2018-10-20 07:10

1 楼

https://soulmachine.gitbooks.io/system-design/content/cn/bigdata/heavy-
hitters.html
从算法角度，上面文章说用hashmap + heap. 可是heap只能告诉你 max value. 你每次
给出top K 不是吧这个heap 摧毁了吗（pop off all values from heap)?难道每次再
重建一边?

n*s2018-10-20 07:10

2 楼

刷题要仔细，还要动脑筋。文里说了是“小根堆”, size k, 取最小值。
你这样面试时问题稍微拐个弯就得懵了。

P*e2018-10-20 07:10

3 楼

明白了。确实是我没看仔细。可是如果用了最小堆，只能解决“每次来一个新的成员如
果比现有最小成员大，剔除现有最小成员，把新成员加入”的问题，要return top K,
每次要把这个堆的每个元素都pop()出来，这样一来这个堆不久摧毁了, 以后还要
return top K 怎么处理? 难道每次pop()出来，return top k, 再放回去?
还有，如果考虑数据量太大单机一个heap放不下，放入几个机器里做好几个heap，最后
汇总到另外一台机器上的global heap. 如果每个单机都用的是最小堆，怎么汇总？汇
总时候难道不需要把每个单机上最大的item放到global heap上马？min heap 找最大
item 不又要吧所有item都pop() 掉？