网站正在建设 下载,铜陵app网站做招聘信息,阿里云oss做视频网站,网站开发自我介绍文章目录 源码是如何插入的#xff1f;扩容向上调整实现大根堆代码#xff1a; 源码是如何插入的#xff1f; 扩容 在扩容的时候#xff0c;如果容量小于64#xff0c;那就2倍多2的扩容#xff1b;如果大于64#xff0c;那就1.5倍扩容。 还会进行溢出的判断#xff0c… 文章目录 源码是如何插入的扩容向上调整实现大根堆代码 源码是如何插入的 扩容 在扩容的时候如果容量小于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 ComparatorInteger {Overridepublic int compare(Integer o1, Integer o2) {// 当然写o1.compareTo(o2)仍然是小根堆return o2.compareTo(o1);}
}public class Test {public static void main(String[] args) {PriorityQueueInteger 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();PriorityQueueInteger 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变为大根堆}
}
