优先级队列建立小根堆来解决前K个高频元素（TOP K问题）

缺乏、安全感 2023-10-12 18:34 33阅读 0赞

**目录**

场景一：解决前K个高频元素需要解决如下几个问题：

优先级队列PriorityQueue

堆的定义

题目链接

场景二：亿万级数据取前TOP K / 后TOP K 数据

--------------------

## **场景一：解决前K个高频元素需要解决如下几个问题：** ##

1.记录每一个元素出现的频率 （解决方法：使用**hashmap**来记录元素出现个数）

2.对出现频率次数进行排序 （解决方法：使用优先级队列建立**小根堆**来进行排序）

3.选择前K个排序大的元素 （解决方法：遍历小根堆前K个元素并逆序打印，因为**小顶堆先弹出的是最小的，所以倒序来输出到数组**）

--------------------

问题1：记录出现频率使用hashmap记录次数即可，这里就不过多阐述

问题2：对出现频率次数进行排序使用小根堆来解决问题

### **优先级队列PriorityQueue** ###

**优先级队列PriorityQueue**就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下PriorityQueue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

### **堆的定义** ###

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果**父亲结点是大于等于左右孩子就是大根堆，小于等于左右孩子就是小根堆。**

所以大家经常说的**大根堆（堆头是最大元素）**，**小根堆（堆头是最小元素）。**

如果自己不想代码实现堆的话，就可以直接使用PriorityQueue（优先级队列）就可以了，底层实现都是一样的，**从小到大排就是小根堆，从大到小排就是大根堆**。

> **取最大前TOP K 高频元素就使用优先级队列建立小根堆**
> 
> 原因：定义一个大小为k的大根堆，在每次移动更新大根堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。
> 
> 因此取前TOP K 高频元素就需要建立小根堆,因为小根堆每次更新元素时都是把最小元素弹出去，这样最大元素就保留下来了
> 
> **取最小前TOP K 元素就使用优先级队列建立大根堆**
> 
> 原因：大根堆每次更新元素都是把最大元素弹出去，这样最小元素就保留下来了

问题3：打印前K个高频元素

因为小根堆元素的堆顶元素是最小的，遍历小根堆元素时是从小到大遍历的，小根堆弹出元素先是最小元素弹出，取前K个高频元素就需要逆序打印元素

### **题目链接** ###

> [力扣题目：347. 前 K 个高频元素][347. _ K]

![47f8b36d3a704249a70fb52a31700638.png][]

代码如下：

class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            //思路：使用map记录每个元素的次数，利用优先级队列建立小根堆来解决TOP K问题
            // 大根堆（堆头是最大元素，从大到小排），小根堆（堆头是最小元素，从小到大排）
            Map<Integer,Integer> map = new HashMap<>();
            for(int num : nums){
                map.put(num,map.getOrDefault(num,0)+1);
            }
          
          //建立小根堆（每次插入元素都把最小元素弹出去，即最后保留下来的元素都是大元素）
            PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> map.get(a) - map.get(b)); //lambda表达式
            for(int key : map.keySet()){ //keySet()为返回所有 key 的不重复集合
                queue.offer(key);
                if(queue.size() > k){
                    queue.poll();
                }
            }
    
            //打印小根堆前K个元素，因为小根堆先弹出的是最小的，所以倒序来输出到数组
            int[] array = new int[k];
            for(int i=k-1;i >=0;i--){
                array[i] = queue.poll();
            }
            return array;
        }
    }

## 场景二：亿万级数据取前TOP K / 后TOP K 数据 ##

在亿万级数据时，不可能一个一个数据排序再去取前TOP K 数据，这会大大降低效率。

**有效的方法：**

1、先将这亿万数据划分为一定数量的大分区，每个大分区的数据量相同，然后再把每个大分区进行划分一定数量的小分区，每个小分区数据量相同。

2、对于每一个小分区使用小根堆或者大根堆来得到前TOP K 或者后TOP K 数据元素，最后再合并一个大分区里面所有的小分区

3、然后使用小根堆或者大根堆得到每一个大分区的TOP K元素，最后在进行大分区合并使用小根堆或者大根堆来得到TOP K 数据。

**注意：若亿万数据有许多重复值，可以先使用HashSet 进行去除重复元素 再进行上述操作。**

**对于海量数据处理取TOP K 数据，思路基本上是：必须分块处理，然后再合并起来。**

[347. _ K]: https://leetcode.cn/problems/top-k-frequent-elements/
[47f8b36d3a704249a70fb52a31700638.png]: https://img-blog.csdnimg.cn/47f8b36d3a704249a70fb52a31700638.png