PriorityQueue源码分析
PriorityQueue源码分析
重点知识罗列
-
PriorityQueue 采用数组的形式保存数据,逻辑上采用二叉堆储存
有关二叉堆的实现原理,查看本人博文 Ted 带你学习数据结构 之 二叉堆
-
PriorityQueue 数组排序并非按照插入顺序,而是需要根据比较器判断; 插入自定义对象时,自定义对象需要实现Comparable接口 ,或者使用外部比较器对象,外部比较器对象需实现Compartor接口
关于比较器详细介绍,可参考本人博文ompareable接口和Compartor接口对比分析 -
PriorityQueue 不能加入null值
-
PriorityQueue 插入和删除原理代码实现
代码选取jdk1.8
① PriorityQueue 属性
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
transient int modCount = 0;
由上可知 : PriorityQueue 里面维护了一个Object数组对象 ,且默大小为11
② 构造器
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
由上可知: 构造一个 PriorityQueue对象,按照默认11个尺寸创建Object[] 数组,且如果没有传入比较器Comparator对象,为null ;
③ 添加对象
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException(); // 这是该对象不能加入null值最好例证
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1); //扩容方法
size = i + 1;
if (i == 0)
queue[0] = e; //如果数组里没数据,此时把数据放在第一位
else
siftUp(i, e); // 保持二叉堆结构,调整方法
return true;
}
上面方法中,主要调了grow()方法,和sitUp()方法,我们深入研究下
private void grow(int minCapacity) {
int oldCapacity = queue.length;
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// 当小于64时,表示堆高在6层内时,每次扩容为原来的1倍+2 ,当大于6层时,每次扩容原来的50%
// 层高计算方式为 H=log(Length) ,但当length为2的次方时,H=log(Length)+1
//上面64,因为是2的6次方,代入到公式中为log64+1 =7,但为为是<号,所以实则表示6层,未到7层
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
siftUp()方法,需要判断有没有比较器,我们就以siftUpUsingComparator(k, x)为例
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;
}
这段代码,有点意思,我们来细撸一下
通过 (k-1)>>>1,位移运算符,获得父节点的索引,然后得到它的值 Object e ,比较父节点e和传入的对象x,如果,子节点比父节点大,那么,break跳出while循环 ; 但如果子节点值不如父节点,那么,它们的值交换位置,并且,此时,仍在while循环里面,会层层和父节点比较,如果发生父节点比子节点大的情况,会一直交换值,直到对象x,到达堆顶
(4)删除对象
poll方法的原理, 从堆顶册除对象a,并且堆中最末位b对象替换堆顶值,然后下沉排序,(拿到根节点下的左右节点,并且判断左右节点的大小,b如果值>子节点,和子节点中中最小值进行替换,循环)
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result; //下沉排序
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, 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;
}
(5)取值
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
取值方法,很好理解了,就是拿到堆顶的值。