景县做个油管的网站怎么做,建行官网网站,鄞州区建设局网站,龙泉驿区城乡建设局网站1、前言
1、优先队列#xff0c;底层通过数组来构造树#xff08;二叉树) 来实现的。
2、默认是最小堆#xff08;取出来的是最小值)#xff0c;可以通过传入一个比较器 comparator 来构造一个最大堆。
3、传入的参数不能为空#xff0c;否则抛出NPE问题。
4、最大堆的…1、前言
1、优先队列底层通过数组来构造树二叉树) 来实现的。
2、默认是最小堆取出来的是最小值)可以通过传入一个比较器 comparator 来构造一个最大堆。
3、传入的参数不能为空否则抛出NPE问题。
4、最大堆的特性是左右孩子的值都比父节点小 最小堆是左右节点值都比父节点大利用该特性可以用来解决一些topK问题
2、关键常量
// 初始化容量
private static final int DEFAULT_INITIAL_CAPACITY 11;// 最小堆和最大堆的比较器 默认是最小堆
private final Comparator? super E comparator;// 数据存储的数组构造成树后节点在数组的index 可以通过以下公式求出
// leftNo parentNo*21 左节点的index
// rightNo parentNo*22 右节点的index
// parentNo (nodeNo-1)/2 //父节点的index , nodeNo当前节点的index
transient Object[] queue;// 最大数组可分配的大小 这里 - 8 是因为一些虚拟机在数组中会保留头部字段
// 如果不 -8分配大小的时候有可能导致OutOfMemoryError
private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;
3、源码解析
下边记录下对一些方法的理解。
3.1、扩容 /*** 扩容** param minCapacity 期望的最小容量*/private void grow(int minCapacity) {int oldCapacity queue.length;// 扩容两倍如果还是小那么而外加 50%int newCapacity oldCapacity ((oldCapacity 64) ?(oldCapacity 2) :(oldCapacity 1));// 防止新容量大于数组的最大容量if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);queue Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity 0) // 最小容量 0 抛出异常throw new OutOfMemoryError();return (minCapacity MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}
3.2、add 方法
public boolean add(E e) {return offer(e);}/*** 入队不能插入 null 元素*/public boolean offer(E e) {// 传入null元素抛异常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;}/*** 插入值后根据比较器进行结构调整,维持堆的特性向上调整*/private void siftUp(int k, E x) {if (comparator ! null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}/*** 最小堆的结构调整,从k指定的位置开始* 将x逐层与当前点的parent进行比较并交换直到满足x queue[parent]为止。* 注意这里的比较可以是元素的自然顺序也可以是依靠比较器的顺序。*/private void siftUpComparable(int k, E x) {Comparable? super E key (Comparable? super E) x;// k 指定的位置indexwhile (k 0) {// 根据公式求出 parentNo (nodeNo-1)/2 父节点的 indexint parent (k - 1) 1;Object e queue[parent];// 从k当前位置的parent进行值比较如果x 大于 parent 就停止循环。(最小堆子节点不能小于父节点if (key.compareTo((E) e) 0)break;// 交换值queue[k] e;k parent;}queue[k] key;}/** link siftUpComparable() 方法差不多根据传入比较器值的大小来进行堆的结构调整* 可能是最大堆也可能是最小堆*/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;}
关于堆siftUp的结构调整如下图所示图来自https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/8-PriorityQueue.md 3.3、peek() // 获取堆顶元素public E peek() {return (size 0) ? null : (E) queue[0];}
3.4、poll() /** 弹出堆的第一个元素同时将最后一个元素置 null , 然后进行堆的结构调整向下调整。*/public E poll() {if (size 0)return null;int s --size;modCount;// 获取堆第一个元素E result (E) queue[0];// 获取堆最后一个元素将其置nullE x (E) queue[s];queue[s] null;// 堆的结构调整if (s ! 0)siftDown(0, x);return result;}/*** 插入 x 的值放在 k 的位置上为了保证堆的特性根据比较器来进行调整堆的结构。* * param k 要插入的位置* param x 要插入的值*/private void siftDown(int k, E x) {if (comparator ! null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x);}/** 堆结构向下调整从k指定的位置开始* 将x逐层向下与当前点的左右孩子中较小的那个交换直到x小于或等于左右孩子中的任何一个为止。*/private void siftDownComparable(int k, E x) {Comparable? super E key (Comparable? super E)x;// 获取数组的中点位置int half size 1; // loop while a non-leafwhile (k half) {// 获取k左孩子的index(假设左孩子是最小的)int child (k 1) 1; Object c queue[child];// 获取k右孩子的index, 为左孩子index 1int right child 1;// 将 x 逐层向下与当前点的左右孩子中较小的那个交换// 直到 x 小于或等于左右孩子中的任何一个为止if (right size ((Comparable? super E) c).compareTo((E) queue[right]) 0)// 左右孩子最小节点的值c queue[child right];// 如果父节点比孩子节点还小则结束循环if (key.compareTo((E) c) 0)break;// 交互当前父节点和比较小节点的值queue[k] c;// 记录孩子节点的index 继续循环k child;}// 最终把k节点也就是父节点放在合适的位置上维持堆的特性queue[k] key;}/** 根据用户构造的比较器向下调整堆结构从k指定的位置开始* 将x逐层向下与当前点的左右孩子中较小的那个交换直到x小于或等于左右孩子中的任何一个为止。*/private void siftDownUsingComparator(int k, E x) {// 获取数组的中点位置int half size 1;while (k half) {int child (k 1) 1;Object c queue[child];int right child 1;if (right size // 使用用户自定义的比较器进行比较comparator.compare((E) c, (E) queue[right]) 0)c queue[child right];if (comparator.compare(x, (E) c) 0)break;// 交换值queue[k] c;k child;}queue[k] x;}关于堆的向下调整大概图如下所示图来着https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/8-PriorityQueue.md 3.5、remove()
// 删除元素如果元素不存在返回falsepublic boolean remove(Object o) {int i indexOf(o);if (i -1)return false;else {removeAt(i);return true;}}// 遍历查找元素是否存在于队列中存在则返回其索引 否则返回-1private int indexOf(Object o) {if (o ! null) {for (int i 0; i size; i)if (o.equals(queue[i]))return i;}return -1;}// 根据索引删除元素private E removeAt(int i) {// 假设索引大于等于0 同时索引小于数组大小modCount;int s --size;// 如果元素刚好是最后一个直接置 null 即可if (s i)queue[i] null;else {// 找到最后的一个元素保存最后一个元素的值然后删除该值E moved (E) queue[s];queue[s] null;// 这时候需要向下调整堆的结构siftDown(i, moved);// 如果当前索引i的值还等于调整前最后一个元素的值if (queue[i] moved) {// 向上调整siftUp(i, moved);// 调整完之后如果当前索引i的值不等于调整前最后一个元素的值if (queue[i] ! moved)// 返回删除的元素的值return moved;}}// 没找到返回nullreturn null;}
removei堆调整的大概图如下所示图来自https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/8-PriorityQueue.md 手动结束线~~~~~~~
对于其它方法感兴趣的朋友可以自行去研究下。
4、参考
JCFInternals/markdown/8-PriorityQueue.md at master · CarpenterLee/JCFInternals · GitHub大佬的集合源码分析写的很nice,图都来自这上面的。
