Solution 中 leetcode 题目 347. Top K Frequent Elements 疑问

Question

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 的最大堆的最后一个元素比较才对。

代码地址：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/08-Heap-and-Priority-Queue/04-Extract-and-Sift-Down-in-Heap/src/Solution.java

Answer 1

liuyubobobo 2018-11-08 13:41:30

程序逻辑是没有问题的，可以尝试提交给Leetcode，可以获得AC：）当然，也可以尝试使用自己的测试用例进行测试。

Solution中的Freq内部类中的compareTo方法，定义了，对于Freq对象来说，频率越小，越大。（代码行数270-278）所以，每次maxHeap.findMax取出的，是当前堆中频率最小的元素。else if部分的语意是：每次找到当前堆中频率最小的元素，如果当前的频率比堆中频率最小的元素要大，则替换：）

在这里，使用MaxHeap看似有点儿绕，所以实际，通常会把堆，包装成优先队列。我们要做的事情是定义优先级。在这里，相当于是，频率越小，优先级越高。

这也就是我在课程里说的，虽然我们可以再写一个最小堆，但其实，使用最大堆，就能完成最小堆的效果，关键在于，大小是人为定义的。我们可以说1比2大，也可以说1比2小；放到优先队列里，就是，我们可以说1比2优先级高，也可以说1比2优先级低，关键看在你的使用场景，怎么定义。

在这里，这个程序主要是用于测试我们写的MaxHeap，我就没有再把他包装成优先队列了：）

• 提问者 晓之海绵宝宝 #1

  非常感谢！

• 提问者 晓之海绵宝宝 #2

  明白了，原来是 compareTo 这里对大小做了相反的定义