PriorityQueue源码分析
大约 2 分钟java基础集合框架
概述
PriorityQueue是一个具有优先级的队列,可根据实现Comparable
定制优先级规则,底层的数据结构为堆,默认使用小根堆。
注
大根堆:在二叉树中,所有根节点大于子节点。
小根堆:在二叉树中,所有子节点大于根节点。
具体可参考下图所示
方法解析
add&offer方法
public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; //如果当前大小不够,扩容。 if (i >= queue.length) grow(i + 1); //调整 siftUp(i, e); size = i + 1; return true; }
首先判断是否需要扩容,扩容实现与ArrayList一致,申请一个新的数组,并将数据复制到新数组
调整堆结构。因为新加的数据会破坏堆结构,因此需要调整堆结构,具体实现如下:
private static <T> void siftUpUsingComparator( int k, T x, Object[] es, Comparator<? super T> cmp) { while (k > 0) { //父节点=(nodeNo-1)/2 int parent = (k - 1) >>> 1; Object e = es[parent]; if (cmp.compare(x, (T) e) >= 0) break; es[k] = e; k = parent; } es[k] = x; }
调整的过程为** : 从
k
指定的位置开始,将x
逐层与当前点的parent
进行比较并交换,直到满足x >= queue[parent]
为止。注意
注意: 这里的比较可以是元素的自然顺序,也可以是依靠比较器的顺序
element&peek
获取队列第一个元素,获取根节点的数据。
public E peek() { return (E) queue[0]; }
remove&poll
public E poll() { if (size == 0) return null; int s = --size; modCount++; //0下标处的那个元素就是最小的那个 E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) //调整 siftDown(0, x); return result; } //siftDown() private void siftDown(int k, E x) { int half = size >>> 1; while (k < half) { //首先找到左右孩子中较小的那个,记录到c里,并用child记录其下标 //左孩子 = parentNo*2+1 //右孩子 = parentNo*2+2 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; //然后用c取代原来的值 queue[k] = c; k = child; } queue[k] = x; }
流程:将队列最后一个位置数据放到第一个位置,然后与左右孩子比较,直至找到自己的位置,满足堆结构为止。
总结
- PriorityQueue底层数据结构为堆,默认为小根堆,可继承Comparable实现自定义的权值排序规则。