【数据结构】堆的初始化——如何初始化一个大根堆？

源码是如何插入的？

扩容

在扩容的时候，如果容量小于64，那就2倍多2的扩容；如果大于64，那就1.5倍扩容。

还会进行溢出的判断，如果决定的新容量大于给的数组最大容量，那就将其限制在数组最大容量:

向上调整

在进行向上调整的时候，会对传进来的comparator进行判断，如果不为空，那就使用程序员传进来的比较器接口，如果为空，那就说明调用者并未实现比较器，那么就使用java自己提供的函数siftUpComparable(k, x）；

传进来的x就是要插入的值e。

这是使用程序员自己传进来的比较器进行比较，调用了compare接口进行比较，所以要想初始化一个大根堆，那就得自己写出一个compare函数然后传进去。

在使用自己写的compare函数时，会让x强转为Comparable类型，如果这个x不是可以比较的（未实现Comparable接口，那就会抛出类型转换异常）

实现大根堆

值得说明的是：
比较器函数是Comparator而不是Comparable。

代码：

import java.util.Comparator;
import java.util.PriorityQueue;class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {// 当然，写o1.compareTo(o2)仍然是小根堆return o2.compareTo(o1);}
}public class Test {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);priorityQueue.offer(4);System.out.print(priorityQueue.poll());System.out.print(priorityQueue.poll());System.out.print(priorityQueue.poll());System.out.println(priorityQueue.poll());// 1 2 3 4，可以发现java中提供的默认堆是小根堆System.out.println("======");PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(new IntCmp());priorityQueue1.offer(1);priorityQueue1.offer(2);priorityQueue1.offer(3);priorityQueue1.offer(4);System.out.print(priorityQueue1.poll());System.out.print(priorityQueue1.poll());System.out.print(priorityQueue1.poll());System.out.print(priorityQueue1.poll());// 4 3 2 1，变为大根堆}
}