JDK源码研究PriorityQueue（优先队列）

Priority Queue

 

目的：

通过对JDK源码的分析，进一步了解堆和优先队列，体会JDK源码的优美之处。

目录：

        1：概念

        2：源码结构

        3：方法分析

概念：

概念1：堆

堆，n个关键字序列K1，K2，…，Kn，当且仅当该序列满足如下性质称为堆

ki≤K2i且ki≤K2i+1（最小堆） 或 (2)Ki≥K2i且ki≥K2i+1 (最大堆)

堆一般用顺序存储结构存储（数组），但逻辑上可以认为是一个完全二叉树。

概念2：优先队列

优先队列，不同于普通的遵循FIFO(先进先出)规则的队列,每次都选出优先级最高的元素出队，优先队列里实际是维护了这样的一个堆，通过堆使得每次取出的元素总是最小的（用户可以自定义比较方法，相当于用户设定优先级）。

 

源码结构

   字段

 

//默认初始化大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//堆
private transient Object[] queue;
//当前大小
private int size = 0;
//比较器
private final Comparator<? super E> comparator;
//修改次数（增、删、改、查）
private transient int modCount = 0;

   方法    

//增加
public boolean add(E e) 
//出队（不删除）
public E peek()
//出队（删除）
public E poll()
//删除
public boolean remove(Object o)
//是否包含某元素
public boolean contains(Object o)
//清空
public void clear()
//扩容
private void grow(int minCapacity)
//查找
private int indexOf(Object o)

方法分析

1：增加

堆在增加元素后，需要进行调整才能维护其最大堆或者最小堆的性质，下面以最小堆为例：

       增加元素26，默认是从队尾增加，即直接添加到数组最后。下一步需要执行上滤。从上图可以看出，26比其父节点39小，因此两者交换位置；再次比较此时的26和其父节点30，30>26,调整位置，依次进行直到找到比26小的父节点，结束。

代码：

 add

public boolean add(E e) {
        return offer(e);
    }

   可以看出，add方法实际上是全部委托给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
	        size = i + 1;
	        //调整
	        if (i == 0)
	            queue[0] = e;//无父节点 ，直接赋值
	        else
	            siftUp(i, e);//有父节点，需要上滤
	        return true;
	    }

    第1步：判空

if (e == null)
    throw new NullPointerException();

    第2步:改变大小和扩容

 modCount++;
 int i = size;
 if (i >= queue.length)
     grow(i + 1);
 size = i + 1;

   第3步：添加元素并上滤

if (i == 0)
    queue[0] = e;
else
    siftUp(i, e);

  从上面的3步中可以看出，实际上关键的步骤是：grow 和 siftUp

  grow方法

	private void grow(int minCapacity) {
		if (minCapacity < 0) // overflow
			throw new OutOfMemoryError();
		int oldCapacity = queue.length;
		// Double size if small; else grow by 50%
		int newCapacity = ((oldCapacity < 64) ? ((oldCapacity + 1) * 2)
				: ((oldCapacity / 2) * 3));
		if (newCapacity < 0) // overflow
			newCapacity = Integer.MAX_VALUE;
		if (newCapacity < minCapacity)
			newCapacity = minCapacity;
		queue = Arrays.copyOf(queue, newCapacity);
	}

1：扩容方式是：

   当前队列大小queue.length<64，则增加一倍容量；反之则增加一半容量。

 2：调用Arrays的copyOf函数 ，实际上调用了该函数

  

 这是个native方法。（注意，该方法只是浅克隆）

siftUp 方法

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

根据不同的比较方式，采取不同比较策略。

下面以使用默认comparator的方式分析

	    private void siftUpComparable(int k, E x) {
	        Comparable<? super E> key = (Comparable<? super E>) x;
	        //k>0保证元素有父节点
	        while (k > 0) {
	        	//父节点下标
	            int parent = (k - 1) >>> 1;
	            Object e = queue[parent];
	            //如果比父节点大，不需要移动，结束
	            if (key.compareTo((E) e) >= 0)
	                break;
	            //父节点元素下移
	            queue[k] = e;
	            //改变k的位置
	            k = parent;
	        }
	        //找到key对一个的合适的位置k，赋值
	        queue[k] = key;
	    }

   可以看出，该方法是采用迭代的方式，找到元素x的位置。

 int parent = (k - 1) >>> 1;
 Object e = queue[parent];

   通过无符号移位操作，取得父节点位置

 if (key.compareTo((E) e) >= 0)
	 break;
  queue[k] = e;
  k = parent;

  此处采用了默认的comparator

  如果比父节点值大，结束。

   如果比父节点值小，父节点值下沉，K重新赋值，直到k=0或者k结点的值大于或等于parent结点值。

2：出队（不删除）

    public E peek() {
        if (size == 0)
            return null;
        return (E) queue[0];
    }

 这个很简单，只是取出了其中的首位元素，但是并没有删除，不需要调整堆。

3：出队（删除最小元素）

出队过程

当最小元素14出队，从数组尾处取39赋值给队首。之后，进行和增加元素后相反的动作即下滤。

首先选出根节点（父节点）39的两个孩子结点中较小者，和39交换位置；当39找到新位置后，执行同种方法，如果孩子结点为null或者都比39大，则结束。

代码：

	public E poll() {
		// 优先队列为空，返回null
		if (size == 0)
			return null;
		int s = --size;
		modCount++;
		// 取出队首
		E result = (E) queue[0];
		E x = (E) queue[s];
		// 队尾赋值为null
		queue[s] = null;
		// 判断是否执行下滤
		if (s != 0)
		    siftDown(0, x);
		return result;
	}

 可以看出其中主要方法是siftDown方法

	private void siftDown(int k, E x) {
	    if (comparator != null)
		siftDownUsingComparator(k, x);
	    else
		siftDownComparable(k, x);
	}

  同样，和上滤一样，是根据不同的comparator采取不同措施比较

    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;
            /如果右孩子小于左孩子，c重新赋值为右孩子的值
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
           // c和key（父节点）比较，若父节点大，不需要移动，结束
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            //改变k的位置，向下移动
            k = child;
        }
        queue[k] = x;
    }

 如果自上向下调整的位置k大于half，说明该结点是叶子结点，直接将x元素赋值给queue[k].

如果自上向下调整的位置k小于half，则递归调整。首先取出左右孩子结点，并取两者中较小者赋值给c，然后比较c和当前k处元素key，如果key小，则结束。如果c大，则将k和c调换位置，经过多次迭代后，当x应该存放在叶子结点上或者x的值小于其左右孩子节点时终止

4：删除

  删除有两种情况：

    情况1：

  此处是执行下滤过程。

 情况2：

此处是执行上滤过程。

	private E removeAt(int i) {
		assert i >= 0 && i < size;
		modCount++;
		int s = --size;
		// 如果是最后一个元素，直接赋值null
		if (s == i)
			queue[i] = null;
		else {
			// 取最后一个元素后，最后位置赋值为null
			E moved = (E) queue[s];
			queue[s] = null;
			// 执行下滤
			siftDown(i, moved);
			// 如果下滤后元素位置没变，说明moved是该子树最小元素；之后需要执行上滤
			// 上滤和下滤实际效果是只会执行其中一个
			if (queue[i] == moved) {
				siftUp(i, moved);
				if (queue[i] != moved)// iterator中会用到此处
					return moved;
			}
		}
		return null;
	}

 如果删除的是最后一个元素，则将最后一个元素设为null

if (s == i)
    queue[i] = null;

 如果删除的不是最后一个元素，取出最后一个元素，并将最后一个元素设为null。执行向下调整函数  siftDown.

E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);

 如果执行了下滤之后，如情况2，此时24并没有向下移动，此时说明需要进行上滤过程

if (queue[i] == moved) {
	siftUp(i, moved);
	if (queue[i] != moved)// iterator中会用到此处
	return moved;
}

 5：clear：清除

这个很简单，只是遍历数组，删除（设为null）

    public void clear() {
        modCount++;
        for (int i = 0; i < size; i++)
            queue[i] = null;
        size = 0;
    }

 6：contains：是否包含

这个过程实际上就是查找过程

    public boolean contains(Object o) {
	return indexOf(o) != -1;
    }

 7:idnexOf ：查找

    private int indexOf(Object o) {
	if (o != null) {
            //遍历数组查询
            for (int i = 0; i < size; i++)
                //如果是自定义的元素，重写equals方法是很有必要的
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

以上只是简单的分析了主要的方法，对于构造函数，实际上主要就是调用这几个方法，就没有再分析。有兴趣可以自行分析，相信会有所收获。

 

   （ps：写完后，准备提交结果出现此种情况

    原因是：

  幸好有自动保存草稿功能，否则....）