使用堆解决常见的TOK问题

关于常见的TOPK问题，都可以使用堆这种数据结构来巧妙的解决，除了去统计最大的或者最小的K个元素

之外，还有一些变形的问题，比如统计出现频率TOPK的问题，这种问题一般需要进行排序。下面列出leetcode

上一些典型的例题：

理解了堆的特点后，解决这些问题并不难，但是我们要熟悉一些堆的基本操作，比如如何生成一个堆、对

堆中的元素进行排序等。此外，在满足复杂度要求的前提下，如何写出更加简练的代码也是一个关注点。毫无

疑问的是在对数据的处理上，python比Java有着先天的优势，在代码编写方面会更加简洁，下面是例题

一、前K个高频元素

给定一个非空的整数数组，返回其中出现频率前 *k* 高的元素

对于这种求TOPK频率的问题，与以往的求最大的K个元素不同，我们需要用哈希表来存放每个元素及其出

现的频率，再用堆这种数据结构去按照升序排列，代码如下：

//构建一个哈希表用来存放每个元素及其出现的频率
private HashMap<Integer,Integer> map = new HashMap(); 

//构建一个小顶堆，并且该堆要对map中的元素出现的频率进行排序
private PriorityQueue<Integer> heap = new PriorityQueue<>((n1,n2) -> map.get(n1) map.get(n2));

//返回的列表
private List<Integer> topK = new LinkedList();
public List<Integer> topKFrequent(int[] nums, int k) {
    //先统计每个元素及其出现的频率，当然还有更简单的写法，请看拓展内容
    for(int n : nums){
            if(map.containsKey(n)){
                map.put(n,map.get(n) + 1);
            }else{
                map.put(n,0);
            }
        }
    
    //按照元素出现的频率进行排序
     for(int n : map.keySet()){
            heap.add(n);
            if(heap.size() > k){
                heap.poll();
            }
        }
     while(!heap.isEmpty()){
            //每次都取出堆顶的元素，也就是出现频率最小的元素首位，
            //这样每个列表中元素就是按照频率从大到小进行排序的
            topK.addFirst(heap.poll());  
        }
        return topK;
    }

拓展：统计每个元素出现频率更简单的写法：

//使用getOrDefault()方法，JDK8中新增的方法
//意思就是当map集合中有这个key时，就使用这个key值，如果没有就使用默认值defaultValue
for (int n: nums) {
    map.put(n, map.getOrDefault(n, 0) + 1);
}

当然我们也可以用python来实现：

def topKFrequent(self, nums, k):
    #Python中的Collections中Counter可以对元素出现的频率从大到小排序，返回的是一个字典
    count = collections.Counter(nums)
    #将count的键值集合转化成一个堆，按照对对应的值（频率）取出前K个最高的元素
	return heapq.nlargest(k, count.keys(), key=count.get)

#拓展
heapq.nlargest(n,iterable[,key]) 
#从迭代器对象iterable返回的前n个最大的元素列表，其中关键字参数key用于匹配是字典对象的iterable，
#可用于更加复杂的数据结构

复杂度的分析：建立一个哈希表并统计出现频率的时间复杂度为O（n）,建堆和输出的复杂度均为

O（Nlog(k)），所有总的时间复杂度为O（Nlog(k)）,是要小于O（NlogN）的；当k比较大的时候，我

们可以将算法改成删除频率最低的如干个元素； 算法的整个过程中用到了哈希表存储数据，空间复杂

度为O(n)，返回的列表为O(k)，所以总共还是O（n）

二、前K个高频的单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。

如果不同的单词有相同出现频率，按字母顺序排序

这个问题与上一个问题是相似的，只需需要进行两级排序即可，代码与前题类似

//这里只写出新建堆关于排序规则的代码
PriorityQueue<String> heap = new PriorityQueue<String>(
    (o1,o2) -> map.get(o1).equals(map.get(o2))? o2.compareTo(o1):map.get(o1) - map.get(o2)
);
//如果出现的频率相同就按照字符串大小进行比较（首字母排序），不同就升序排序（小顶堆）

复杂度的分析与前题相同

三、数据流中的中位数 leetcode 295

计算取出数据流中的中位数

这个问题使用堆可以很好的解决，因为中位数就是数据流进行排序后，中间两个数的平均数（数据流的

个数为偶数）的平均值，或者中间那个数（数据流的个数为奇数）。我们不需要对整个数据流进行排序，只

需保证中间的那个数比它左边的所有树都大，比其右边的所有数都小即可

我们可以维护两个堆，一个小顶堆，待存放的是比中位数大的数据；另一个大顶堆，存放的是比中位数

小的数据，当待添加的数据是偶数个时，可以将其先添加到小顶堆中，但如何保证这个元素要比所有大顶堆

中的元素大呢，就是需要先将其插入大顶堆中，再将大顶堆中的首个元素添加到小顶堆；同理，当数据是第

奇数个时，可以将其加入到大顶堆中，但是如何保证这个元素比所有小顶堆中的元素小呢，就需要先将其

插入到小顶堆中，在将小顶堆中的首个元素添加到大顶堆中

等到将数据流处理完毕后，就可以求中位数了，如果数据个数为偶数，那就取小顶堆和大顶堆的中间值

的平均值，如果数据个数为奇数，那就取小顶堆的首个元素，因为先插入小顶堆的。代码如下：

    //大顶堆，存储左半边元素
    private PriorityQueue<Integer> left = new PriorityQueue<>((o1,o2) -> o2 - o1);
    //小顶堆，存储右半边的元素，且右半边的元素大于左半边的元素
    private PriorityQueue<Integer> right = new PriorityQueue<>();
    //当前数据流中读入元素的个数
    private int N = 0;
    /** initialize your data structure here. */
    public MedianFinder() {
    }
    
    //插入要保证两个堆都处于平衡状态
    public void addNum(int num) {
        if(N%2 == 0){
            left.add(num);    
            right.add(left.poll());    //先插入小顶堆
        }else{
            right.add(num);
            left.add(right.poll());   //再插入大顶堆
        }
        N++;
    }
    
    public double findMedian() {
        if(N % 2 == 0){
            return (left.peek() + right.peek())/2.0;
        }else{
            return (double)right.peek();
        }
    }
}