PriorityQueue 优先队列

 

其内部其实是一个最小堆

最小堆具有三个特性：

1.最小堆是完全二叉树。

2.任意节点如果有左右孩子，那么它的值必须小于或者等于左右孩子的值。

3.任意非叶子节点的左右子树也都是堆。

图示举例：

而最小堆可以由数组或者二叉链表实现，通过源码可知PriorityQueue是使用的数组实现最小堆。

transient Object[] queue;

因此queue[n]节点的左孩子为queue[2n+1],右孩子为queue[2n+2]。但需要小心是否数组越界！

也可以因此推导，queue[m]的父节点下标是  queue[(m-1)/2] 。因为Java中整数运算存在向下取整现象，因此针对左右孩子均满足。但注意当m=0时 (m-1)/2为0，但根节点不存在所谓的父节点，这样计算是错误的。

 

当对PriorityQueue进行迭代遍历时会发生什么？

调用PriorityQueue的 iterator()方法时，返回的是一个名为Itr的内部类，这个类实现了Iterator接口并且被声明为private final class 。并在内部利用cursor指针迭代内部数组queue。

简单来说就是对queue数组进行了一次遍历。

 

当对PriorityQueue进行插入时会发生什么？

调用add()或者offer()方法均可，因为本质上add()内部就是调用的offer()函数。

插入元素时分情况考虑，并且总是插入到堆的末尾。

 

堆为空：

直接插入，无需扩容，无需调整。（构造函数中初始化queue，默认初始容量11）

堆不为空：

1.判断是否需要扩容，需要的话则调用grow方法。

2.插入元素后可能会破坏堆的平衡，调用siftUp(上滤)方法调整堆，直到平衡。

 

public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) //实际大小超过queue容量时进行扩容 grow(i + 1); size = i + 1; if (i == 0) //堆为空时 queue[0] = e; else //堆不空时，上滤调整 siftUp(i, e); return true; }

 

gorw扩容原理

与ArrayList扩容方式类似

若数组容量小于64，则扩大为原来的2倍

若数组容量大于等于64，则扩大为原来的1.5倍

最后还要检查新容量不能大于MAX_ARRAY_SIZE (为int的最大值-8，-8是在序列化的情况下有的JVM实现需要预留一个头部写入数组大小，不-8的话有可能造成数组越界)

且将原数组内容拷贝到新数组中，并丢弃原数组中内容

private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); }

 

siftUp()原理

自底向上，不断地比较，交换

 

这里假设插入的元素为e

首先将e插入到queue末尾，再不断地比较e与父节点p的关系

若 e < p则交换，且将指针回溯到p

若e >= p则表示当前位置合适，并终止

//在k位置插入元素x 一般情况k是size+1 时间复杂度O(logN) 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; }

 

poll方法原理

即弹出堆顶元素，并将末尾元素直接放到堆顶，size-- 

再调用siftDown(下滤)进行堆调整

 

siftDown原理

自顶向下，使堆再平衡

直到下标越界

节点的值要同时小于左孩子及右孩子（选其中最小的交换）

//k为插入位置，一般情况是0 x为插入元素 时间复杂度O(logN) private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // 取size中间值 while (k < half) { //当k大于一半的size时表示没有左右孩子 int child = (k << 1) + 1; Object c = queue[child]; //选出左孩子 int right = child + 1; 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; k = child; } queue[k] = key; }

 

无序数组建堆过程

queue中存的数组本就无序

//时间复杂度不是O(NlogN) 而是O(N) private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); }