【Java集合源码】PriorityQueue源码分析

1、结构体系

PriorityQueue属于Queue集合体系，为优先队列。队列是一种先进先出的数据结构。而优先队列，它的元素出队顺序与元素的优先级有关。其内部根据维护一个大根堆或小根堆，默认情况是小根堆

2、二叉堆

在理解PriorityQueue前，有必要先理解何为二叉堆。

【数据结构】二叉堆

理解PriorityQueue，首先要了解两个最基本的操作

1. 上浮（siftUp）

   添加元素后，上浮进行二叉堆的再平衡

2. 下沉 （siftDown）

   删除元素后，下沉进行二叉堆的再平衡

3、主要参数

//默认容量大小
	private static final int DEFAULT_INITIAL_CAPACITY = 11;
    //保存元素的数组，同样是一个二叉堆
    transient Object[] queue; // non-private to simplify nested class access
    //集合元素数量
    private int size = 0;
	//比较器，自定义比较逻辑，决定是大根堆还是小根堆
    private final Comparator<? super E> comparator;
    //集合修改次数
    transient int modCount = 0; 
           

根据几个成员变量，可以知晓PriorityQueue内部使用数组实现二叉堆，默认的容量大小为11

4、构造函数

//空参构造器
	public PriorityQueue() {
		//比较器为null
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
	
	//自定义初始化容量
	public PriorityQueue(int initialCapacity) {
		//比较器为null
        this(initialCapacity, null);
    }

	//自定义比较器
	public PriorityQueue(Comparator<? super E> comparator) {
		//使用默认容量
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

	//自定义容量和比较器
	public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
           

5、add方法

public boolean add(E e) {
		//直接调用offer方法
        return offer(e);
    }
           

6、offer方法

//入队方法
	public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        //修改次数加1
        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;
    }
           

7、grow方法

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));
        //为了防止溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
       	//元素拷贝
        queue = Arrays.copyOf(queue, newCapacity);
    }
           

扩容的本质是利用Arrays.copyOf方法进行元素复制，重点在于新数组的大小

• oldCapacity < 64 -> newCapacity = oldCapacity * 2 + 2
• oldCapacity > 64 -> newCapacity = 1.5 * oldCapacity
• newCapacity > 2147483639，newCapacity = Integer.MAX_VALUE

8、siftUp方法

private void siftUp(int k, E x) {
        if (comparator != null)
        	//使用初始化的比较器进行上浮
            siftUpUsingComparator(k, x);
        else
        	//使用默认的比较器进行上浮
            siftUpComparable(k, x);
    }
           

9、siftUpComparable方法

private void siftUpComparable(int k, E x) {
		//将对象强转成Comparable，从而可以使用compareTo方法进行比较
        Comparable<? super E> key = (Comparable<? super E>) x;
        //k即为当前循环的子节点的下标
        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;
    }
           

10、poll方法

将堆顶元素出队，并通过下沉操作使二叉堆再平衡

public E poll() {
        if (size == 0)
        	//队列中元素总个数为0，直接返回null结束
            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;
    }
           

11、siftDown方法

private void siftDown(int k, E x) {
 		//比较器不为null，使用比较器进行下沉
        if (comparator != null)
            siftDownUsingComparator(k, x);
        //否则，使用Comparable进行比较并下沉
        else
            siftDownComparable(k, x);
    }
           

12、siftDownComparable方法

private void siftDownComparable(int k, E x) {
 		//强转，使用compareTo方法进行比较
        Comparable<? super E> key = (Comparable<? super 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 &&
                ((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;
    }