Solution 中 leetcode 题目 347. Top K Frequent Elements 疑问
来源：8-4 从堆中取出元素和Sift Down
晓之海绵宝宝
2018-11-08
MaxHeap<Freq> maxHeap = new MaxHeap<>();
for(int key: map.keySet()){
if(maxHeap.size() < k)
maxHeap.add(new Freq(key, map.get(key)));
else if(map.get(key) > maxHeap.findMax().freq){
maxHeap.extractMax();
maxHeap.add(new Freq(key, map.get(key)));
}
}
用最大堆处理的 else if 分支中，将 map 中的元素与最大堆的 root 节点比较是否正确？我觉得应该是与元素数量 k 的最大堆的最后一个元素比较才对。
写回答
1回答
-
程序逻辑是没有问题的，可以尝试提交给Leetcode，可以获得AC：）当然，也可以尝试使用自己的测试用例进行测试。
Solution中的Freq内部类中的compareTo方法，定义了，对于Freq对象来说，频率越小，越大。（代码行数270-278）所以，每次maxHeap.findMax取出的，是当前堆中频率最小的元素。else if部分的语意是：每次找到当前堆中频率最小的元素，如果当前的频率比堆中频率最小的元素要大，则替换：）
在这里，使用MaxHeap看似有点儿绕，所以实际，通常会把堆，包装成优先队列。我们要做的事情是定义优先级。在这里，相当于是，频率越小，优先级越高。
这也就是我在课程里说的，虽然我们可以再写一个最小堆，但其实，使用最大堆，就能完成最小堆的效果，关键在于，大小是人为定义的。我们可以说1比2大，也可以说1比2小；放到优先队列里，就是，我们可以说1比2优先级高，也可以说1比2优先级低，关键看在你的使用场景，怎么定义。
在这里，这个程序主要是用于测试我们写的MaxHeap，我就没有再把他包装成优先队列了：）
022018-11-08
相似问题
leetcode 3号题
回答 2
关于TOP K 问题
回答 1