本文主要是介绍Java-PriorityQueue源码分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
PriorityQueue 源码分析
Java中的PriorityQueue采用的是堆这种数据结构来实现的,而存储堆采用的则是数组。
堆是一个完全二叉树,堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值,对于每个节点的值都大于等于子树中每个节点值的堆,我们叫做大顶堆,对于每个节点的值都小于等于子树中每个节点值的堆,我们叫做小顶堆。
如何实现一个堆
可以看出来,数组中下标为i的节点,其左子节点就是下标为 i*2+1
的节点,右子节点则是下标为 i*2+2
的节点。
新增
新增的时候,我们将插入的数据暂时放置到数组中的最后一个位置,运气好的话,它就刚好满足堆特性,也不需要移动元素了。不好的话就需要移动元素位置了。
移动过程如下:新插入的节点与父节点比较大小,如果不满足子节点大于等于父节点的大小关系(小顶堆),则互换两个节点,一直重复这个过程,直到父子节点满足刚才说的那种关系。
PriorityQueue数据结构如下:
public class PriorityQueue<E> extends AbstractQueue<E>implements java.io.Serializable {private static final int DEFAULT_INITIAL_CAPACITY = 11;// 数组/*** Priority queue represented as a balanced binary heap: the two* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The* priority queue is ordered by comparator, or by the elements'* natural ordering, if comparator is null: For each node n in the* heap and each descendant d of n, n <= d. The element with the* lowest value is in queue[0], assuming the queue is nonempty.*//*优先级队列表示为平衡的二进制堆:两者队列[n]的子队列是左子树队列[2*n+1]和右子数队列[2*(n+1)]。的优先级队列由比较器或元素的自然排序,如果comparator为空:对于中每个节点n和n的每个后代d, n <= d最小值在队列[0]中,假设队列非空。*/transient Object[] queue;// 数组中元素个数private int size = 0;}
总结下插入元素时的主要过程
-
判断插入元素是否为空,为空则抛出空指针异常
-
在判断数组是否需要扩容,如果是则进行扩容
-
如果是第一次插入元素,则放入数组的第一个位置
-
如果不是则进行堆化过程
-
- 找到父节点位置 : (k-1) >>> 1
- 判断插入元素的值是否大于父节点(小顶堆),如果是则结束堆化过程
- 如果不是则交换元素位置
- 持续上面的1,2,3步骤,直到插入的节点已经是堆顶结点(k==0)
public boolean add(E e) {return offer(e);
}// 如果插入空元素,则抛出空指针异常
public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;if (i >= queue.length) //扩容grow(i + 1);size = i + 1;// 第一次插入放入数组的第一个位置(下标从0开始)if (i == 0)queue[0] = e;else siftUp(i, e); //堆化过程return true;
}// 如果插入元素超过队列的长度,则进行扩容: 如果小于64双倍扩容,大于等于50%
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 codeif (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);
}private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {// 1. 父节点位置 (k-1)/2,这里采用无符号右移(值为整数)int parent = (k - 1) >>> 1;Object e = queue[parent];// 2. 如果要插入的元素大于父节点元素的值,则结束堆化过程if (key.compareTo((E) e) >= 0)break;// 3. 交换元素位置queue[k] = e;k = parent;}queue[k] = key;
}
删除
对于小顶堆而言,当删除堆顶元素之后,就需要把第二小的元素放到堆顶,那么第二小的元素就会出现在左右子节点中。当删除后,如果我们还是迭代的从左右子节点中选择最小元素放入堆顶,就会造成数组空洞,我用下面的图来演示这个问题。
我们可以在删除堆顶元素的时候,将最后一个元素拿来补位。由于在堆化的过程中,都是交换操作,就不会出现数组空洞了。
// k=0, x=queue[size-1]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) {int child = (k << 1) + 1; // assume left child is least// 找到左右子节点中小的那个节点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;
}
这篇关于Java-PriorityQueue源码分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!