一.堆排序:我们该如何借助堆来对数组的内容来进行排序呢？

假设我们现在有一个数组，要求从小到大进行排序，我们是需要进行建立一个大堆还是建立一个小堆呢？

1)我的第一步的思路就是建立一个小堆，因为每一次堆顶上面的元素就是最小的元素，直接按照顺序进行弹出堆顶元素不就可以了吗

2)但是当前我们要对数组整体本身进行排序，将来的数组，0下标就是最小的元素，不是每一次依次输出最小的元素，不是从小到大进行输出

总结:我们是将数组从小到大进行排序，那么我们建立一个大根堆，如果将数组按照从大到小进行排序，那么我们就建立一个小根堆，如果想让数组从小到大进行排序，那么就建立成一个大根堆

1)先进行把数组元素调整成大根堆，因为我们以后进行数据的交换的时候，总是要把最大的元素放到数组的最后一个位置

2)我们让堆的根节点也就是0小标和数组的最后一个位置未排序的元素进行交换即可，这样就可以保证数组的最后一个end位置一定是当前堆的最大元素，数组的最后一个位置一定是原数组中最大的元素

3)调整成大根堆，因为此时只有根节点的元素所在的位置不是一个大根堆，那么就向下进行调整这棵树

4)定义一个end值等于数组有效数据的长度，并且重复和堆顶元素进行交换，向下进行调整

5)例如我们想要对数组进行从大到小进行排序，那么我们要建立一个大堆；

建立大堆的时间复杂度是O(N)，空间复杂度是O(1)

这个代码是错误的,自己去细细地品吧;public void sort(){int len=usedsize;while(len!=0){int temp=array[len-1];array[len-1]=array[0];array[0]=temp;len--;adjustDown(0,len);}

  public void heartsort(){int index=usedsize-1;while(index!=0)//让顶上的元素与末尾元素交换，在对啊让arr1[0]进行向上调整{int temp=arr1[0];arr1[0]=arr1[index];arr1[index]=temp;downadjust(0,index);index--;}}

三:TopK问题

1)有十万个数据，你给我找前十个最大的数据？假设你的数据在内存中是可以进行存放的

思路1:建立一个大堆，弹出堆顶元素10次

就是将所有元素建立一个大堆，既然是找前10个最大的数据，那么就需要pop()10次就可以了(缺点:有多少个数据，堆就有多大)，建堆的时间复杂度是O(N)，每一次进行向下进行调整的时间复杂度是log(N)，所以时间复杂度就是K*logN，其中的logN是向下进行调整的高度

思路2:建立一个大小为K的小堆

1)将前10个数据建立一个大小为10的小堆，遍历剩下的元素如果元素比堆顶元素大，就入堆，同时删除堆顶元素，再将剩下的元素调整成一个小堆；

2)当前我们找的是前十个最大的数据，那么我们为什么要建立一个小堆呢？

因为此时堆顶的元素，一定是当前K个元素中最小的元素，如果有元素比当前的堆顶元素大，那么这个元素很有可能就是Topk中的一个；

3)当我们要找第K大的元素的时候，首先我们要建立一个小堆，遍历剩下的元素，不断地进行比较，最终堆顶元素就是第K小的元素；

时间复杂度:我们要进行遍历这个数组中的所有元素，所以说时间复杂度是O(N)，每当我们进行遍历到一个元素的时候，我们都要进行出堆顶元素，并且进行向下调整，每一次进行向下调整的次数是logK，所以说整个TopK问题的时间复杂度就是N*logK

思路:求前K大的元素 

1)先把前K个元素，建立成一个小根堆

2)遍历后面的元素，只要当前遍历的元素比堆顶元素大，就进行弹出堆顶元素，将遍历到的这个元素这个元素入堆操作

3)将这个元素进行入堆之后，我们可以继续将这个堆中的元素，调整成一个小根堆

TopK问题的解决思路:比如说求前K个最小的元素

1)创建一个大小为K的大根堆

2)遍历数组中的元素，将前K个元素放入到队列里面

3)从K+1个元素开始，每一个元素都和堆顶元素进行比较，先弹出，后压入

 

总结:

1)如果说求前K个最大的元素，我们要构建一个小根堆，如果遍历的元素比堆顶的元素大，那么就将它入堆，重新调整成一个小根堆

2)如果说我们求前K个最小的元素，我们需要构建大根堆，如果说遍历的元素比堆顶的元素小，那么就将它入堆，重新调整成一个大根堆

3)如果需要求第K大的元素，建一个小堆，进行遍历原来的数组，最终得到的堆顶元素就是第K大的元素

4)PriorityQueue在进行插入元素的时候，是不可以进行插入null值的，因为我们要进行插入的元素要可以进行比较，况且要有可比较的能力，那么我们如何向优先级队列里面存放自定义元素呢？那么我们这个自定义的类必须事先Compareable接口或者是是Comparator接口

static void TopK(int[]arr1){//创建一个大小为K的大根堆PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(3, new Comparator<Integer>() {
//他的意思就是说有一个类,实现了Comparator接口,并且重写了compare方法,相当于就是匿名内部类@Overridepublic int compare(Integer o1, Integer o2) {return o1-o2;//小堆是o1-o2,大堆是o2-o1}});for(int i=0;i<arr1.length;i++){
//遍历数组中的元素,将前K个元素放到队列里面if(priorityQueue.size()<3){priorityQueue.add(arr1[i]);}else{int num=priorityQueue.peek();
//代码走到这里面,说明队列中已经存放了三个元素了
//从第K+1个元素开始,每一个元素都要和当前堆顶元素进行比较
//先找到当前堆顶的元素，如果这个元素比数组元素大,就取出对顶元素,放数组元素入队列if(arr1[i]>num){
//先进行弹出,在进行存入priorityQueue.poll();priorityQueue.add(arr1[i]);}}}System.out.println(priorityQueue);int array[]=new int[k];for(int i=0;i<array.length;i++){int data=queue.poll();array[i]=data;}}public static void main(String[] args) {int arr1[]={34,23,89,78,123,67,87,55};
//写一个topk问题，找到数组中8个数中前三个最大的TopK(arr1);}

 public static void main(String[] args) {PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}});int[] array={10,90,100,110,89,78};InsertQueue(array,queue);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());}private static void InsertQueue(int[] array, PriorityQueue<Integer> queue) {for(int i=0;i<array.length;i++){queue.offer(array[i]);}}

 

前K个最大的数对:力扣

这个题还是用TopK来进行解决，我们还是先要创建一个大堆，但是此时优先级队列中放的就不是一个数字了，他存放的是一个数对，也就是说，优先级队列中的每一个元素是一个List<Integer>，以后遍历元素的时候，我们就需要比较的值是每一个List中的两个元素的和；

 class Hello{public static void main(String[] args) {int arr1[]={1,7,11};int arr2[]={2,4,6};PriorityQueue<List<Integer>> priorityQueue=new PriorityQueue<>(3, new Comparator<List<Integer>>() {@Overridepublic int compare(List<Integer> o1, List<Integer> o2) {return o2.get(0)+o2.get(1)-o1.get(0)-o1.get(1);}});for(int i=0;i<arr1.length;i++){for(int j=0;j<arr2.length;j++) {if(priorityQueue.size()<3){ArrayList list=new ArrayList<>();list.add(arr1[i]);list.add(arr2[j]);priorityQueue.add(list);}else{int top=priorityQueue.peek().get(0)+priorityQueue.peek().get(1);if(top>arr1[i]+arr2[j]){priorityQueue.poll();ArrayList list=new ArrayList<>();list.add(arr1[i]);list.add(arr2[j]);list.addAll(list);}}}}List<List<Integer>> list1=new ArrayList<>();for(int k=0;k<3&&!priorityQueue.isEmpty();k++){list1.add(priorityQueue.poll());}System.out.println(list1);}

练习:前K个高频单词

题目关键:返回的答案应该按单词出现频率由高到低进行排序,咱们建的是小堆

如果有不同的单词按照相同的出现频率，应该按照字典顺序来进行排序

1)我们遍历原来的哈希表，我们创建一个HashMap里面进行记录每一个字符串出现的次数

2)相当于现在待排序序列是哈希表中的每一个(Key-Value)键值对，我们要根据写键值对来进行建立一个小堆(本质上来说是依靠单词出现的次数建立一个小堆)

3)频率高低为前提，频率高低相同比较字典大小，字典小的入堆

package Demo;import java.util.*;class Solution {public List<String> topKFrequent(String[] words, int k) {HashMap<String,Integer> map=new HashMap<>();for(int i=0;i<words.length;i++){if(!map.containsKey(words[i])){map.put(words[i],1);}else{int count=map.get(words[i]);count++;map.put(words[i],count);}}PriorityQueue<Map.Entry<String,Integer>> queue=new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {if(o1.getValue().compareTo(o2.getValue())==0){return o2.getKey().compareTo(o1.getKey());//当放的元素小于堆的个数处理的时候变成大堆;a-2,b-2;}return o1.getValue()-o2.getValue();//核心是根据value值进行比较的}});for(Map.Entry<String,Integer> entry:map.entrySet()){if(queue.size()<k){queue.add(entry);//放入元素的时候会自动帮助我们建立一个大堆}else{Map.Entry<String,Integer> s1=queue.peek();if(entry.getValue().compareTo(s1.getValue())>0){//先看比较堆顶元素和即将要存放的元素出现频率大小queue.poll();queue.add(entry);}else if(entry.getValue().compareTo(s1.getValue())==0){//当频率相同的时候,比较长度if(entry.getKey().compareTo(s1.getKey())<0) {//单次顺序在后面的入堆queue.poll();queue.add(entry);}}}}List<String> list=new ArrayList<>();// System.out.println(queue);while(!queue.isEmpty()){Map.Entry<String,Integer> entry=queue.poll();list.add(entry.getKey());}Collections.reverse(list);return list;}
}

对象排序的比较以及PriorityQueue的部分源码

一:向优先级队列里面添加元素:offer的源码

public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);size = i + 1;if (i == 0)queue[0] = e;elsesiftUp(i, e);return true;}

优先级队列的扩容以及容量问题:

1)当你调用不带有参数的构造方法的时候，默认容量就是11，况且他默认传入的comparator比较器就是空

2)对于优先级队列的扩容，用grow函数进行扩容，如果原来数组的长度小于64，那么以原来的长度的2倍+2进行扩容，如果原来的容量不是小于64的，反之就要以1.5倍进行扩容

存放数据:

3)当我们进行第一次存放元素的时候，会先把第一个元素直接放到底层的queue的0下标、

4)当我们不是第一次存放的时候，会调用siftUp方法，第一个参数是即将要放到数组下标的位置，第二个参数就是要具体存放的引用(对象)

o1就是新存放的元素

 private void siftUp(int k, E x) {//k==2,e等于自定义类型if (comparator != null)
//这里面的comparotor是优先级队列中的一个属性,是我们需要在构造方法中进行传入的,在这里面会进行指定比较类型siftUpUsingComparator(k, x);else
//如果我们没有进行传入comparator比较器,那么最终会默认把我们传输过来的自定义类型强制转化成Comparable类型siftUpComparable(k, x);}
//假设我们在创建一个优先级队列的时候,既没有向里面传入一个比较器,自定义类型还没有实现Compareator接口,那么最后当我们向队列中存放第二个元素的时候,此时就会发生报错

由于我们使用的是无参的构造方法，没有进行传入一个比较器，所以在上面就会调用siftUpComparable()方法

  @SuppressWarnings("unchecked")private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {int parent = (k - 1) >>> 1;//计算父亲节点的下标Object e = queue[parent];if (key.compareTo((E) e) >= 0)
//这个布尔表达式为假就进行交换,为真就不会进行交换break;queue[k] = e;k = parent;}queue[k] = key;}@SuppressWarnings("unchecked")private void siftUpUsingComparator(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = x;}

1)如果说一个没有实现Comparator接口，构建优先级队列的时候还没有进行传一个比较器，那么代码就会抛出，这个类 cannot be cast to java.lang.Comparable

2)上述代码第一行会把对象转化成比较器，在while循环里面会调用compareTo方法

3)如果进入到循环里面，break出去，就不会进行交换，如果可以正确执行到break之后的代码，就可以正确的进行交换了

4)如果换成大堆，直接把compareTo方法的return顺序换一下，这个时候 PriorityQueue是大堆还是小堆完全取决于自定义类实现比较接口的compareTo的方法是怎么写的

1)我们在正常情况下priorityQueue使用的是Compareable接口，当我们没有传入任何的比较器的时候，默认的就是使用Compareable接口，会将元素转化成Compable类型，在进行向上调整的时候，使用了自定义类重写的CompareTo()方法，但是我们要对比较的类实现Compareable接口，这样对于类的侵入性太强了，一旦写好了根据那一种规则进行修改，就不可以进行发生变化了

public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}
public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}
public PriorityQueue(Comparator<? super E> comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator);}

上面的默认两种方法都是基于compareable接口来进行实现的

2)我们自己可以写一个比较器，所以之前默认构造方法就不可以用了，咱们需要自己写一个比较器:

1)public PriorityQueue(Comparator<? super E> comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator)
2)public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {}

里面的while循环都是用compare方法，建立大堆或者小堆都是依靠return语句里面的写法

class AgeComparator implements Comparator<Student>{public int compare(Student o1,Student o2){return o1.age-o2.age;}
}
class Student{public int age;public String username;public Student(int age,String username){this.age=age;this.username=username;}
}
public class Main{public static void main(String[] args) {AgeComparator comparator=new AgeComparator();PriorityQueue<Student> queue=new PriorityQueue<>(3,comparator);}   
}

4)自定义类型的比较，一定要实现比较接口；

5)父类的equals方法默认比较的是地址，但是在类中重写equals方法进行比较，比较的是对象里面的内容，先比较两个引用是不是同一种类型，在比较他们具体的内容；

创建小堆o1-o2;创建大堆o2-o1;

@Override
public boolean equals(Object o) {if (this == o) return true;//判断他们是否是地址相同,也就是说看看他们是否引用的是同一个对象if (o == null || getClass() != o.getClass()) return false;
//看看他们的类对象是否相同,是不是属于同一个类创建的两个对象,比较他们的类型//接下来我们要把Object类型转化成Student类型Student student = (Student) o;
//比较它们是否对象内容相同return age == student.age && Objects.equals(name, student.name);
}

对于String重写equals方法:

 public boolean equals(Object anObject) {if (this == anObject) {return true;//判断他们是否是地址相同,也就是说看看他们是否引用的是同一个对象}if (anObject instanceof String) {
//如果说anObject也是一个字符串类型的,就进入到if语句里面进行下一步的比较String anotherString = (String)anObject;
//将Object类型转化成字符串类型int n = value.length;if (n == anotherString.value.length) //在这里面判断他们的长度是否相同
{
//在进行取出两个字符串的每一个字符一一进行比较,如果不相等,那么就直接返回falsechar v1[] = value;char v2[] = anotherString.value;int i = 0;while (n-- != 0) {if (v1[i] != v2[i])return false;i++;}return true;}}return false;}