TopK问题常见题型为求最大（最小）的K个值。
我们一般拿堆来解决。
堆：二叉堆首先是一颗完全二叉树
二叉堆结点间的关系满足：
大根堆： 根节点是整棵树的最大值，对于它的任意子树，堆中根节点的值>=子树中的结点值。
小根堆： 根节点是整棵树的最小值，对于它的任意子树，堆中根节点的值<=子树中的结点值。
TopK题型解决：取大用小，取小用大。
（取前100个比较小的树用大根堆，
取前100个比较大的树用小根堆）
实现一个大根堆：
package ds.bin_tree.bin_tree_heap;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxHeap {
List arr;
public MaxHeap()
{
this(10);
}
//初始化堆大小
public MaxHeap(int size)
{
arr=new ArrayList<>(size);
}
public void siftUp(int k)
{
//上浮条件：结点值大于父节点值||走到根结点
while (k>0&&arr.get(k)>arr.get(parent(k)))
{
swap(k,parent(k));
k=parent(k);
}
}
public MaxHeap(int[] arr2)
{
arr=new ArrayList<>(arr2.length);
MaxHeap maxHeap=new MaxHeap();
for (int i:arr2)
{
arr.add(i);
}
//从最后一个非叶子结点开始，依次进行元素下沉
for (int i=parent(arr.size()-1);i>=0;i--)
{
siftDown(i);
}
}
public void siftDown(int k)
{
//终止条件：走到叶子结点了，k的左子树已经大于数组长度了
while (leftTree(k)arr.get(i))
{
i=i+1;
}
if (arr.get(k)>arr.get(i))
{
break;
}
else
{
swap(k,i);
k=i;
}
}
}
public int extractMax()
{
if (isEmpty())
{
throw new NoSuchElementException("heap is empty");
}
int max=arr.get(0);
arr.set(0,arr.get(arr.size()-1));
arr.remove(arr.size()-1);
siftDown(0);
return max;
}
public int peekMax()
{
if (isEmpty())
{
throw new NoSuchElementException("heap is empty");
}
return arr.get(0);
}
private void swap(int i, int j) {
int temp=arr.get(i);
//arr.set(元素下标，元素值）
arr.set(i,arr.get(j));
arr.set(j,temp);
}
public void add(int val)
{
arr.add(val);
siftUp(arr.size()-1);
}
private int parent(int k)
{
return (k-1)/2;
}
private boolean isEmpty()
{
return arr.size()==0;
}
private int leftTree(int k)
{
return (2*k)+1;
}
public int rightTree(int k)
{
return (2*k)+2;
}
@Override
public String toString() {
return arr.toString();
}
}
优先级队列：看起来是队列，底层是基于堆的实现，按照元素的优先级大小动态出队。
（JDK内置优先级是最小堆）
package ds.bin_tree.bin_tree_heap;
import java.util.*;
import java.util.PriorityQueue;
public class PriorityQueueTest {
public static void main(String[] args) {
//通过构造方法传入比较器
//默认是最小堆，“值”（比较器comparator返回的值）越小，优先级越高
//传入降序比较器。
// Queue queue=new PriorityQueue<>(new StudentComDesc());
//匿名内部类，创建一个Comparator接口的子类，这个子类只使用一次
Queue queue=new PriorityQueue<>(new Comparator()
{
@Override
public int compare(Student o1, Student o2) {
return o1.getAge()- o2.getAge();
}
});
//Lambda表达式，函数式编程
// Queue queue=new PriorityQueue<>((o1, o2) -> o1.getAge()-o2.getAge());
Student stu = new Student("张三", 19);
Student stu2 = new Student("李四", 27);
Student stu3 = new Student("王五", 25);
queue.offer(stu);
queue.offer(stu2);
queue.offer(stu3);
while (!queue.isEmpty())
{
System.out.println(queue.poll());
}
// Student[] students={stu,stu2,stu3};
// Arrays.sort(students);
// System.out.println(Arrays.toString(students));
// System.out.println(stu.compareTo(stu2));
// System.out.println(stu.compareTo(stu3));
// Student[] students={stu,stu2,stu3};
// Arrays.sort(students,new StudentCom());
// System.out.println(Arrays.toString(students));
}
}
//从小到大顺序
class StudentCom implements Comparator
{
@Override
public int compare(Student o1, Student o2) {
return o1.getAge()-o2.getAge();
}
}
//从大到小顺序
class StudentComDesc implements Comparator
{
@Override
public int compare(Student o1, Student o2) {
return o2.getAge()-o1.getAge();
}
}
class Student
{
private String name;
private int age;
public Student(String name,int age)
{
this.age=age;
this.name=name;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + ''' +
", age=" + age +
'}';
}
}
Comparable和Compator区别：
比较器Compartor：新建一个类来对内容进行比较。
一个类实现了Comparabe接口，说明该类具备了可比较大小的能力。类本身具备可比较能力。
如：
class Student implements ComparableTopK问题：{ private String name; private int age; public Student(String name,int age) { this.name=name; this.age=age; } public String getName() { return name; } public int getAge() { return age; } @Override public String toString() { return "student{" + "name='" + name + ''' + ", age=" + age + '}'; } @Override public int compareTo(Student o) { return this.getAge()-o.getAge(); } }
package ds.bin_tree.bin_tree_heap.leetcode;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class Num17_14 {
public int[] smallestK(int[] arr, int k) {
if (arr.length==0||k==0)
{
return new int[0];
}
//构造一个最大堆，JDK默认最小堆，使用比较器改为最大堆。
Queue queue=new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i:arr)
{
if (queue.size()peek)
{
continue;
}
//当前元素<堆顶元素，先出队，再把当前元素入队
else
{
queue.poll();
queue.offer(i);
}
}
}
int[] ret=new int[k];
for (int i=0;i
package ds.bin_tree.bin_tree_heap.leetcode;
import java.util.*;
public class Num347 {
private class Freq implements Comparable
{
private int key;
private int times;
public Freq(int key, int times) {
this.key = key;
this.times = times;
}
@Override
public int compareTo(Freq o) {
return this.times-o.times;
}
}
public int[] topKFrequent(int[] nums, int k) {
int[] ret=new int[k];
Map map=new HashMap<>();
for (int i:nums)
{
//遍历数组，如果i存在，取得存在的次数再+1，不存在,给一个默认值0 ，次数为0再+1;
map.put(i, map.getOrDefault(i,0)+1);
}
//扫描map集合，将前k个最高频率放入优先级中
Queue queue=new PriorityQueue<>();
for (Map.Entryentry: map.entrySet())
{
if (queue.size()entry.getValue())
{
continue;
}
else
{
queue.poll();
queue.offer(new Freq(entry.getKey(),entry.getValue()));
}
}
}
for (int i=0;i
package ds.bin_tree.bin_tree_heap.leetcode;
import java.util.*;
public class Num373 {
private class Pair
{
//第一个数组中的数
int u;
//第二个数组中的数
int v;
public Pair(int u, int v) {
this.u = u;
this.v = v;
}
}
//前k个最小元素构建大根堆
public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue queue=new PriorityQueue<>(new Comparator() {
@Override
public int compare(Pair o1, Pair o2) {
return (o2.u+ o2.v)-(o1.u+o1.v);
}
});
for (int i=0;i(pair.u+ pair.v))
{
continue;
}
else {
queue.poll();
queue.offer(new Pair(nums1[i],nums2[j] ));
}
}
}
}
List> ret=new ArrayList<>();
//当k>数组长度的时候（例如有两个数对，k=3;)不可能出队三次，终止条件要加上！queue.isEmpty
for (int i = 0; i < k&&(!queue.isEmpty()); i++) {
List temp=new ArrayList<>();
Pair pair=queue.poll();
temp.add(pair.u);
temp.add(pair.v);
ret.add(temp);
}
Collections.reverse(ret);
return ret;
}
}
