JAVA源码详解之优先队列PriorityQueue（逐行注释）

前言

优先队列是JAVA以堆排序为基础实现的数据结构，这种结构在删除或新增元素后，会自动进行重排，非常方便。本文分析优先队列中的常用方法源码来加强理解。

堆排序

所谓堆，是一种完全二叉树。如果这颗树的父节点值大于等于子节点值，则称为大顶堆。如果父节点值小于等于子节点，则成为小顶堆。

算法

1、将序列中的n个元素构造成堆

2、堆顶与序列末尾元素交换，这样末尾元素就成了整个序列的最大（最小）值

3、对当前序列的前n-1个元素重复1和2

有关堆排序的详解可以参考这篇文章。

源码解析

变量

//默认容量11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//队列中元素的数量
private int size = 0;
//定义比较规则 不传该参数时 默认使用小顶堆
private final Comparator<? super E> comparator;
//底层使用数组保存队列元素
transient Object[] queue;
//堆的重新结构化次数
transient int modCount = 0; 

对offer()、poll()、remove()这3个方法及它们的关联方法进行分析，其他方法都很简单，直接看源码即可。

offer(E e) 方法

增加元素

每次调用offer()方法时，队列已经是堆的状态的了，offer的元素先假定放在队尾，然后自下向上重构堆

public boolean offer(E e) {
    //不能增加null元素
    if (e == null)
        throw new NullPointerException();
    modCount++;
    //当前要增加元素的位置 因为数组索引从0开始 所以取size即可
    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;
}

siftUp(int k, E x) 自下向上 重构堆

   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) {
           //求出父节点
           int parent = (k - 1) >>> 1;
           //取父节点元素
           Object e = queue[parent];
           //如果要插入的元素比父节点大 结束循环
           if (key.compareTo((E) e) >= 0)
               break;
           //否则 将要插入的元素与父节点交换位置
           queue[k] = e;
           //将k指向父节点 继续向上比较
           k = parent;
       }
       //循环结束 说明k到达了根节点 或者要插入的元素比父节点大了 找到了最终要插入的位置
       queue[k] = key;
   }
//使用自定义比较器 逻辑与上面的默认方法相同
   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;
   }

grow(int minCapacity) 扩容的方法

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 旧容量小于64时 直接翻倍 否则容量增加50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // 超出最大容量时 重设容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //拷贝原数组 并将其数组长度扩充至newCapacity
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

poll()方法

每次取出队首元素后，假定队尾元素放置队首，然后自上向下重构堆

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;
    //如果队列中元素个数大于1 则必定大于0 需要重构堆
    if (s != 0)
        //队尾元素移到队首 进行重构
        siftDown(0, x);
    //否则说明队列中只有一个元素 直接返回即可
    return result;
}

siftDown(int k, E x) 自上向下 重构堆

private void siftDown(int k, E x) {
    if (comparator != null)
        //带比较器
        siftDownUsingComparator(k, x);
    else
        //默认方法
        siftDownComparable(k, x);
}

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    //half为非叶子结点的个数
    //因为堆结构是完全二叉树 设树中度为0的节点个数是n0,度为1的是n1,度为2的个数是n2
    //则n0 + n1 + n2 = n, 又因为二叉树中 n2 + 1 = n0 
    //联立上面的两个等式 得出n0 = (n - n1 + 1) / 2
    //因为完全二叉树中n1等于0或1 所以n0是n/2向上取整
    //所以非叶子结点个数即为n/2向下取整
    int half = size >>> 1;        // loop while a non-leaf
    //只需比较将队尾元素与非叶子结点比较即可
    //这样比较结束之后已经可以保证堆重构完成
    while (k < half) {
        //左孩子结点
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        //取左右孩子中较小的赋值给c
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        //如果key比左右孩子都小 循环结束
        if (key.compareTo((E) c) <= 0)
            break;
        //否则 将较小的孩子结点上移
        queue[k] = c;
        //让k指向孩子结点 继续比较下一层
        k = child;
    }
    //找到了要插入的位置
    queue[k] = key;
}
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;
}

从上述代码中可以看出，调用poll()之后，重构堆时，只是保证了堆顶元素最小，但是左右孩子结点的大小关系不一定，所以底层数组不一定是完全有序的。这本来也是堆结构的性质。我们用一段代码来验证。

PriorityQueue<Integer> queue=new PriorityQueue<>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
System.out.println(Arrays.toString(queue.toArray())); // [1, 2, 3, 4, 5]
queue.poll();//poll之后 队首最小 但是整个队列不是有序的
System.out.println(Arrays.toString(queue.toArray())); // [2, 4, 3, 5]

remove(Object o) 方法

删除指定元素

public boolean remove(Object o) {
    //元素索引
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        //删除元素
        removeAt(i);
        return true;
    }
}

private int indexOf(Object o) {
    if (o != null) {
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

removeAt(int i) 删除指定位置元素

private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
        queue[i] = null;
    else {
        //队尾元素
        E moved = (E) queue[s];
        //队尾删除
        queue[s] = null;
        //以i为根结点 自上向下重构堆
        siftDown(i, moved);
        //queue[i]==move说明moved直接放在了i的位置
        if (queue[i] == moved) {
            //尝试能否向堆的上层移动
            siftUp(i, moved);
            //如果能向上移动 返回moved
            if (queue[i] != moved)
                return moved;
        }
    }
    //如果删除元素后 队尾元素直接放在i的位置就能满足堆结构 那就返回null
    return null;
}

参考文章

https://www.cnblogs.com/chengxiao/p/6129630.html