关于堆解决top-k的问题

Question

如下图，如果要取前5个大的数值得出的答案是62 41 30 28 16，但是实际上28的子节点和30的左节点都比16大，但是用extractMax的方法又会破坏整个堆，没有办法实现数据流动，所以应该做哪些操作？希望老师指点下

Answer 1

liuyubobobo 2018-11-11 13:47:55

这个图我特意造的数据，就是为了让大家不要误解，上层的数据一定大于下面的数据。在堆中，层数没有意义，不能说明数据的大小，只有堆顶元素是最大的。

但是，你的结论不对。从堆中取出前五个元素，是这组数据中的排名前五。16不会被取出，22会被取出。因为extractMax会改变堆中数据的排列结构。在堆中不能取出相应的数组的前五个元素，当做前五名！必须调用5次extractMax！

extractMax不是在破坏堆！恰恰相反，extractMax在维护堆！

抱歉，我没有理解你说的数据流动是什么意思。topk是只做一个包含k个元素的堆，但整体数据可能有n个。n个数据是流动的，堆中所保存的所有元素，是这个数据的前k名。我觉得你堆使用堆解决topk问题的思路没有领结，请动手写一下，请在仔细体会理解一下使用堆解决topK问题思路：）

加油！

• 提问者 哈哈哈蜜瓜 #1

  非常感谢！