[toc]
一、优先队列
普通队列：先进先出，后进后出
优先队列：出队顺序呢入队顺序无关；和优先级相关
优先队列的各种实现比较
| 结构 | 入队 | 出队(拿出最大的元素) |
|---|---|---|
| 普通线性结构 | O(1) | O(n) |
| 顺序线性结构 | O(n) | O(1) |
| 堆 | O(logn) | O(logn) |
二、二叉堆 Binary Heap
- 二叉堆是一个完全二叉树
注意：满二叉树是值除了叶子节点，其他节点都含有左右子节点
完全二叉树：不一定是一个满二叉树，但是缺失的那部分一定在整棵树的右下侧；也就是从上到下，从左到右，一层一层的铺，铺满一层再铺下一层，把元素顺序排列成树的形状，
- 最大堆（同样可以定义最小堆) 堆中某个节点的值，总是不大于其父节点的值(子节点的值永远小于等于父节点的值)
注意：二叉堆不同层元素之间无明确比较性，层级越浅不一定比层级更深的大。
二叉堆(完全二叉树)与数组索引之间的关系
利用动态数组储存二叉堆，从上到下，从左到右，从0开始索引编号，对于第i节点的左孩子的索引为2i + 1 , 右孩子为2i + 2，而对于第i节点的父节点，索引为(i - 1) /2
二叉堆在内存中是以动态数组储存的，而逻辑上是用二叉树的思想实现的
这里用的数组为之前实现的动态数组Array
SiftUP操作：向最大堆中添加节点，先将节点添加到完全二叉树中，然后将节点与父节点比较，如果大于父节点，就进行交换。
SiftDown：从堆中取出元素：具体的算法思想是将堆顶上的值返回，然后将完全二叉树最后一个元素放在堆顶，然后将堆最后一个元素删除。将顶的元素与孩子进行比较，如果不存在左孩子，则不需要置换，如果存在左孩子且存在右孩子且右孩子大于左孩子，则将节点与右孩子进行置换，否则与左孩子进行置换。再根据情况判断是否进入下一个循环。
详细请参考下面的代码MaxHeap类。
replace
取出最大元素后，放入一个新的元素，先将最大元素返回，然后将最大元素替换为一个新的元素，然后进行Sift Down,这样复杂度就变为O(logn)级别的了。
Heapify
通过构造函数实现，传入一个数组，将其转换为一个最大堆，
算法思想：找到完全二叉树中最后一个含有子节点的节点索引(其实就为动态数组最后一个节点的父节点)，以此位置为基础，倒着遍历完全二叉树的节点，反复进行shiftDown操作。这样操作的复杂度为O(logn)
- Array.java 动态数组中添加的部分置换代码
/**一个新的构造函数*/
/** 交换两个索引对应的值 */
public void swap(int i, int j){
if(i < 0 || i >= size || j < 0 || j >= size)
throw new IllegalArgumentException("Index is illegal.");
E t = data[i];
data[i] = data[j];
data[j] = t;
}
- 最大堆
public class MaxHeap<E extends Comparable<E>> {
/**引入之前写的动态数组类Array*/
private Array<E> data;
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
public MaxHeap(){
data = new Array<>();
}
/**返回堆中的元素个数*/
public int size(){
return data.getSize();
}
/**返回一个布尔值，表示堆中是否为空*/
public boolean isEmpty(){
return data.isEmpty();
}
/**找到一个索引的父节点*/
private int parent(int index){
if(index == 0)
throw new IllegalArgumentException("Index-0 doesn't have parent.");
return (index - 1) / 2;
}
/**找到一个索引的左子节点*/
private int leftChild(int index){
return index * 2 + 1;
}
/**找到一个索引的右子节点*/
private int rightChild(int index){
return index * 2 + 2;
}
/**向堆中添加元素 sift up
* 将节点添加到树中，反复与父节点比较，
* 为了满足最大堆可以将其进行反复交换*/
public void add(E e){
data.addLast(e);
siftUp(data.getSize() - 1);
}
private void siftUp(int k){
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
data.swap(k, parent(k));
k = parent(k);
}
}
/** 看堆中的最大元素*/
public E findMax(){
if(data.getSize() == 0)
throw new IllegalArgumentException("Can not findMax when heap is empty.");
return data.get(0);
}
/**取出堆中最大的元素*/
public E extrackMax(){
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
/**shiftDown的思想实现*/
private void siftDown(int k){
// 如果存在左节点则进行循环（不可能只有右节点，这是个完全二叉树）
while(leftChild(k) < data.getSize()){
/**获得最大子节点的索引*/
// j 暂存可能会被替换的索引
int j = leftChild(k);
// 如果右孩子存在且右孩子比左孩子大
if(j + 1 < data.getSize() &&
data.get(j + 1).compareTo(data.get(j)) > 0)
j = rightChild(k);
// data[j] 是leftChild和rightChild中最大的
/**将父节点与最大子节点比较*/
if(data.get(k).compareTo(data.get(j)) >= 0)
break;
data.swap(k, j);
k = j;
}
}
}
三、优先队列
- 优先队列实现的接口
Queue.java
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
- 优先队列的实现
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap<E> maxHeap;
public PriorityQueue(){
maxHeap = new MaxHeap<>();
}
@Override
public int getSize(){
return maxHeap.size();
}
@Override
public boolean isEmpty(){
return this.maxHeap.size() == 0;
}
@Override
public E getFront(){
return maxHeap.findMax();
}
@Override
public void enqueue(E e){
maxHeap.add(e);
}
@Override
public E dequeue(){
return maxHeap.extrackMax();
}
}
- 测试代码
Main.java
import java.util.Random;
public class Main {
public static double testHeap(Integer[] testData, boolean isHeapify){
long startTime = System.nanoTime();
/**指定泛型的类型*/
MaxHeap<Integer> maxHeap;
if(isHeapify)
maxHeap = new MaxHeap<>(testData);
else {
maxHeap = new MaxHeap<>();
for(Integer data : testData)
maxHeap.add(data);
}
int[] arr = new int[testData.length];
for(int i = 0; i < testData.length; i ++)
arr[i] = maxHeap.extrackMax();
for(int i = 1; i < testData.length; i ++){
if(arr[i - 1] < arr[i])
throw new IllegalArgumentException("error");
}
System.out.println("Test MaxHeap completed.");
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] agrs){
int n = 1000000;
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for(int i = 0; i < n; i++)
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
int [] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = maxHeap.extrackMax();
}
for(int i = 1; i < n; i++){
if(arr[i - 1] < arr[i])
throw new IllegalArgumentException("Error");
}
System.out.println("Test MaxHeap completed");
/**============================================*/
int m = 1000000;
Random random2 = new Random();
Integer[] testData = new Integer[m];
for(int i = 0; i < m; i ++){
testData[i] = random2.nextInt(Integer.MAX_VALUE);
}
double time1 = testHeap(testData, false);
System.out.println("Without heapify: " + time1 + " s");
double time2 = testHeap(testData, true);
System.out.println("With heapify: " + time2 + " s");
}
}
四、Leetcode上的347号问题
在N个元素中选出前M个元素(N远远大于M)
并归排序时间复杂度: NlogN
使用优先队列（基于堆）：NlogM
思路：使用优先队列，只维护当前看得到的前M个元素
多态compareTo方法实现。
347号问题：请点击Leecode进行查看
1、用自己实现的最大堆实现
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
public class Solution {
/**重写入堆的优先级，implements了Comparable
* 必须实现compareTo方法*/
private class Freq implements Comparable<Freq> {
private int e, freq;
private Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
/**重写compareTo方法，重新定义优先级的规则
* 从而利用最大堆来储存'最小堆'，这波操作特别六*/
@Override
public int compareTo(Freq another) {
if(this.freq < another.freq)
return 1;
else if(this.freq > another.freq)
return -1;
else
return 0;
}
}
/**List是一个接口，需要制定底层的实现，这里用的ArrayList进行实现的*/
public List<Integer> topKFrequent(int[] nums, int k) {
/**先用map统计词频*/
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int num :nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
/**优先队列，最大堆
* 利用最大堆储存一个最小堆(很神奇是吧)，
* 利用优先队列只保存所需个数的长度，数顶是当前最小频率的数
* 然后将之后遍历得到的频率与最小的比较，如果比最小的大，就将
* 顶的数出队列，然后将当前的入队列并自动排序，当遍历完map中所有
* 的key,优先队列里面保存的就是所需的前频次最高的数*/
PriorityQueue<Freq> pq = new PriorityQueue<>();
for(int key: map.keySet()) {
if(pq.getSize() < k)
pq.enqueue(new Freq(key, map.get(key)));
else if(map.get(key) > pq.getFront().freq) {
pq.dequeue();
pq.enqueue(new Freq(key, map.get(key)));
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.dequeue().e);
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.println(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,1,2,2,2,3,3,3,4,4,6,7,8,0};
int k = 4;
printList((new Solution()).topKFrequent(nums, k));
}
}
2、使用Java标准类库中提供的PriorityQueue(底层是使用的最小堆)实现
- (基础版)使用一个新的类Freq，实现比较接口Comparable进行实现
/**使用Java标准库中 PriorityQueue，是用最小堆实现的
* 但是可以自己传入一个 自定义优先级*/
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
public class MySolution {
public class Freq implements Comparable<Freq> {
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
// 定义优先级，
@Override
public int compareTo(Freq another) {
if(this.freq < another.freq)
return -1;
else if(this.freq > another.freq)
return 1;
else
return 0;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map统计词频
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
// 利用优先队列储存,最小堆，
PriorityQueue<Freq> pq = new PriorityQueue<>();
for(int key: map.keySet()) {
if(pq.size() < k)
pq.add(new Freq(key, map.get(key)));
else if(map.get(key) > pq.peek().freq) {
pq.remove();
pq.add(new Freq(key, map.get(key)));
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.remove().e);
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 2;
printList((new MySolution()).topKFrequent(nums, k));
}
}
- (进阶版)自定义一个比较的方法，交给优先队列(通过构造函数)，告诉优先队列使用自己实现比较的方法
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Comparator;
public class MySolution {
public class Freq {
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
}
/**实现Comparator，定制比较的方法*/
public class FreqComparator implements Comparator<Freq> {
@Override
public int compare(Freq a, Freq b) {
return a.freq - b.freq;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map统计词频
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
// 调用定制比较方法的构造函数。
PriorityQueue<Freq> pq = new PriorityQueue<>(new FreqComparator());
for(int key: map.keySet()) {
if(pq.size() < k)
pq.add(new Freq(key, map.get(key)));
else if(map.get(key) > pq.peek().freq) {
pq.remove();
pq.add(new Freq(key, map.get(key)));
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.remove().e);
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 2;
printList((new MySolution()).topKFrequent(nums, k));
}
}
- (高阶版)在2的基础上使用匿名函数,并去掉Freq类
package maxHeap;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Comparator;
public class MySolution {
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map统计词频
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
// 调用定制比较方法的构造函数。使用匿名函数的方式
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2);
}
});
for(int key: map.keySet()) {
if(pq.size() < k)
pq.add(key);
else if(map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 2;
printList((new MySolution()).topKFrequent(nums, k));
}
}
- (终极牛逼版)使用lamda表达式的方式
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Comparator;
public class MySolution {
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map统计词频
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
/**使用lamda的方式，定义优先队列的优先级*/
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> map.get(a) - map.get(b)
);
for(int key: map.keySet()) {
if(pq.size() < k)
pq.add(key);
else if(map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 3;
printList((new MySolution()).topKFrequent(nums, k));
}
}
五、和堆相关的更多话题和广义队列
| d叉堆 d-ary heap | 索引堆 | 二项堆 | 斐波那契堆 |
|---|---|---|---|
| 时间复杂度为NlogdM,对应的代价就是 | 比较高级 |
- 广义队列 支持一个普遍的接口
广义队列接口.png
普通队列：先进先出
优先队列：优先级高的先出
栈，也可以理解为一个队列
六、整合案例：实现一个比较器来定义二叉堆元素的优先级，默认为最小堆
从底层到测试实现的思路
Array.java :
Array是一个动态数组，可以根据储蓄的容量自动扩容和自动缩容，自动扩容和缩容也进行了边界的优化。这里就不展示全部的代码了在我前面的一篇笔记 动态数组中详细介绍了实现的思路。
MinHeap.java
MinHeap是一个最小堆，基于Array实现的，支持自定义优先级排序只需要在构造方法中传入一个比较器(规定返回值为int,小于等于0则第一个参数的优先级高，否则第二个优先级高)，如果不传入比较器，默认以入堆的元素的最小堆进行排序，并且内部实现了siftUp/shiftDown/replace/Heapify操作
import java.util.Comparator;
/**设计一个最小堆，默认是最小堆，但是支持自定义优先队列的优先级
* 底层是以数组形式储存的，索引从0开始*/
public class MinHeap<E extends Comparable<E>> {
private Array<E> data;
/**接收定义优先级方法，默认使用最小堆进行堆排序
* priority下面的compare接受两个参数compare(E a, E b)
* 统一规定，返回的结果<=0,a的优先级高，反之b的优先级高*/
private Comparator<E> priority;
public MinHeap(int capacity) {
this.data = new Array<>(capacity);
this.priority = null;
}
public MinHeap() {
this.data = new Array<>();
this.priority = null;
}
/**设计一个支持自定义优先级的构造函数
* 需要用户传递一个实现了Comparator接口的类，并且返回int类型*/
public MinHeap(Comparator<E> priority) {
this.data = new Array<>();
this.priority = priority;
}
/**返回堆中的元素个数*/
public int size() {
return data.getSize();
}
/**判断堆是否为空*/
public boolean isEmpty() {
return data.isEmpty();
}
/**找到完全二叉树相应节点的父节点*/
private int parent(int index) {
if(index == 0)
throw new IllegalArgumentException("Index '0' doesn't has a parent!");
return (index - 1) / 2;
}
/**找到一个索引的左子节点*/
private int leftChild(int index) {
return index * 2 + 1;
}
/**找到一个索引的右子节点*/
private int rightChild(int index) {
return index * 2 + 2;
}
public void add(E e) {
data.addLast(e);
siftUp(data.getSize() - 1);
}
/**sift up,将节点添加到完全二叉树的末尾，
* 反复与父节点比较，按照优先级进行交换，
* 直到与满足最小堆*/
private void siftUp(int k) {
/**实现默认情况下的最小堆*/
if(this.priority == null) {
while (k > 0 && data.get(k).compareTo(data.get(parent(k))) < 0) {
data.swap(k, parent(k));
k = parent(k);
}
} else {
/**规定接收定义优先级方法，默认使用最小堆进行堆排序
* priority下面的compare接受两个参数compare(E a, E b)
* 规定，返回的结果<=0,a的优先级高，反之b的优先级高*/
while (k > 0 && priority.compare(data.get(k), data.get(parent(k))) < 0) {
data.swap(k, parent(k));
k = parent(k);
}
}
}
/** shiftDown 操作
* 对于传进来的索引，根据这个索引与其节点最小的子节点
* 进行交换，一直交换到满足最小堆*/
private void siftDown(int k) {
while (leftChild(k) < data.getSize()) {
int j = leftChild(k);
if(j + 1 < data.getSize()) {
/**默认最小堆的情况*/
if(this.priority == null){
if(data.get(j + 1).compareTo(data.get(j)) < 0)
j ++;
} else {
/**规定接收定义优先级方法，默认使用最小堆进行堆排序
* priority下面的compare接受两个参数compare(E a, E b)
* 规定，返回的结果<=0,a的优先级高，反之b的优先级高*/
if(this.priority.compare(data.get(j + 1), data.get(j)) < 0)
j ++;
}
}
/**将父节点与最大子节点比较*/
if(this.priority == null) {
if(data.get(j).compareTo(data.get(k)) < 0)
data.swap(j, k);
} else {
if(this.priority.compare(data.get(j), data.get(k)) < 0)
data.swap(j, k);
}
k = j;
}
}
/**查看堆中的最大元素*/
public E peek() {
if(data.getSize() == 0)
throw new IllegalArgumentException("The minHeap is empty!");
return data.get(0);
}
/**取出堆中最大的元素*/
public E extrackTop() {
E res = this.peek();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return res;
}
/**取出堆中最大的元素，并且替换成元素e*/
public E replace(E e) {
E ret = this.peek();
data.set(0, e);
this.siftDown(0);
return ret;
}
/**Heapify操作,使用构造函数实现*/
public MinHeap(E[] arr) {
data = new Array<>();
for(int i = parent(arr.length - 1); i >= 0; i --) {
siftDown(i);
}
}
}
Queue.java
Queue是普通队列的一个接口
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
PriorityQueue.java
PriorityQueue是基于MinHeap实现的Queue接口的一个优先队列，默认的构造函数创建默认最小堆，带有参数的构造函数创建带有比较器的自定义堆。强烈建议传入一个lamda表达式。
import java.util.Comparator;
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MinHeap<E> minHeap;
public PriorityQueue() {
this.minHeap = new MinHeap<>();
}
/**传入一个自定义优先级，构造函数*/
public PriorityQueue(Comparator<E> priority) {
this.minHeap = new MinHeap<>(priority);
}
@Override
public int getSize() {
return this.minHeap.size();
}
@Override
public boolean isEmpty() {
return this.minHeap.size() == 0;
}
@Override
public E getFront() {
return this.minHeap.peek();
}
@Override
public void enqueue(E e) {
this.minHeap.add(e);
}
@Override
public E dequeue() {
return minHeap.extrackTop();
}
public void replace(E e) {
minHeap.replace(e);
}
}
Main.java
主类进行测试，测试用例是：有一个容量为1000000的装int类型的数组，里面有很多重复的元素，而且是乱序，现在要求快速找出频率最高的前10个元素并打印出来。
很low的思路：我可以先把这1000000排个序，啥冒泡排序啊，选择排序啊，并归排序啊三路块排啊什么什么的，排序后的数组标记为arr1，然后再建立一个装小数组arrL(长度为2)的大数组allB(长度为1000000)，arrL第一个元素用于储存元素，arrL第二个储存统计的频率，遍历arr1,将相关数据储存到arrL,再将arrL装到allB，然后再根据arrL[1]进行从大到小排序，最后取前10个。对应的这种系统开销是非常可观的，对应的时间复杂度大概为O(n^2)级别的。数据量越大，复杂度结果越可怕。。。
牛逼思路：遍历这个数组A，利用标准库中的TreeMap统计各个数组出现的频率，利用优先队列，限制只储存10个元素，根据对应的频率大小确定入队的优先级，储存相关频率对应的数字，采用最小堆(注意，优先队列中储蓄的是数字，储存的数字本身大小不参与优先级的排序，参与排序的是数字对应map中的频率，而且是最小堆，堆顶是10个中频率最小的),遍历TreeMap,将数字存入优先队列，当优先队列中存入了10个元素后，之后遍历的数字与优先队列顶进行优先级比较(比较对应的频率)，如果遍历的数字频率大于顶的频率，就进行replace操作，就是将这个数与顶的数进行交换，然后进行SiftDown
请参照上面的SiftDown操作。遍历完了优先队列中储存的就为频率最大的前10个数。对应的时间复杂度大概为O(nlogm) ，n个数，取前m个数
import java.util.Comparator;
import java.util.Random;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
int[] res0 = {1,1,1,1,1,1,3,3,5,5,5,5,5,5,7,7,8,8,8,8,8,9,0,2,3,4,5,6,7,8,9,0,1};
int m0 = 3;
printArray(findPro(res0, m0));
System.out.println("===================");
/**统计一个容量为n的数组中频次最高的前m个元素
* 时间复杂度估计为O(nlogm), (如果不对请批评指教，我对于时间复杂度的计算不是特别熟)
* 随机生成int类型的数字*/
int n = 1000000;
int m = 10;
int[] res = new int[n];
Random random = new Random();
for(int i = 0; i < n; i ++) {
res[i] = random.nextInt(Integer.MAX_VALUE);
}
printArray(findPro(res, m));
}
/**打印结果*/
public static void printArray(int[] array) {
for(int num : array) {
System.out.print(num + " ");
}
System.out.println();
}
/**通过标准库的treeMap统计词频然后利用自己实现的基于动态
* 数组->最小堆->优先队列统计，使用自定义实现Comparator确定优先级，
* 找出前频次最高的元素*/
public static int[] findPro(int[] array, int k) {
// 利用map统计字频
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int arr : array) {
if(!map.containsKey(arr))
map.put(arr, 1);
else
map.put(arr, map.get(arr) + 1);
}
/**通过优先队列遍历并储蓄m个最高的词频， 抛出的接口表示，
* 返回值<=0，则第一个参数的优先级高。
* 匿名函数 或者 lamda表达式能够访问当前的作用域*/
/** 匿名函数的写法
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2);
}
});*/
/** (高级玩儿法)lamda表达式*/
PriorityQueue<Integer> pq = new PriorityQueue<>(
(Integer o1, Integer o2) -> map.get(o1) - map.get(o2)
);
for(int key : map.keySet()) {
if(pq.getSize() < k) {
pq.enqueue(key);
} else {
if(map.get(key).compareTo(map.get(pq.getFront())) > 0){
pq.replace(key);
}
}
}
int[] ret = new int[k];
for(int i = 0; i < k; i ++) {
ret[i] = pq.dequeue();
}
return ret;
}
}
谢谢阅读，如有错误的地方请批评指出，让大家一起进步！
