Java优先队列源码解析

昨天做LeetCode双周赛的时候，想用优先级队列实现一个排行榜，但是一直出错，发现自己还是对源码看的比较少，今天索性花一些时间看一下这个优先级队列的源码。
第一次写这样的总结，有不对的请指正。
以前也用过优先级队列来实现堆的功能，其实它的内部就是用一个数组来实现的，内部排序和堆排序的功能类似。

transient Object[] queue; 

一、插入元素

首先看向队列中添加元素的过程，可以看到是下面的这个方法，主要过程是先判断队列大小是否超过了数组大小，如果是那么就要进行扩容，如果大小足够，就进行插入。

   public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);//扩容
            //当数组小于64时，扩两倍，大于的时候扩容50%
        size = i + 1;
        if (i == 0)
            queue[0] = e;//设置根节点
        else
            siftUp(i, e);//进行插入
        return true;
    }

在进行插入时，调用了下面的方法，可以看到如果在定义队列时指定了比较器就会以指定方式比较，否则就按自然顺序比较。

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

具体的实现以比较器的版本来看一下，其实都是一样的，就是堆排序中的向上调整。

  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;//将新元素插入合适位置
    }

二、删除元素

删除元素的时候，先获得元素的下标，由于是数组，直接遍历查找。然后将指定位置的元素删除。
注意这里的remove是队列的。

 public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

下面是具体的删除过程。如果是删除最后一个元素，就直接删除，不用调整。如果是删除中间某个元素，则将最后一个元素替换到删除位置，然后做向下调整，使堆重新有序。

    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;  //删除最后一个元素，其实是交换
            siftDown(i, moved); //向下调整
            if (queue[i] == moved) {//如果moved还在这里，说明比较小
                siftUp(i, moved);//对于很小的数字需要向上调整
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

下面是具体的向下调整的过程。

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

和堆排序的过程相似，根据下标位置k进行循环调整，k不会超过节点数的一般，最多到达叶子节点。2k+1是左子节点，2k+2是右子节点。找到节点中比较小的

 private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        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;
            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位置
            k = child;  //k继续向下
        }
        queue[k] = key;//最后找到合适位置
    }

弹出堆顶元素，可以看到和堆排序一样，每次把堆顶元素返回，把最后一个元素放到堆顶后进行下调整。

    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;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

三、迭代器

在遍历优先队列时，常用到迭代器
迭代器是一个内部类，实现了迭代器接口

private final class Itr implements Iterator<E>

内部类中包含一个双端队列，保存在迭代过程中被删除的元素，在迭代完之后，还需要对这个队列进行处理。

private ArrayDeque<E> forgetMeNot = null;

修改次数计数器，用于在迭代过程中看是否有新的插入或删除操作，有就要抛出并发修改异常。

private int expectedModCount = modCount;

判断是否有要遍历的元素，如果下标小于数组大小或者前面那个队列不为空。

public boolean hasNext() {
            return cursor < size ||
                (forgetMeNot != null && !forgetMeNot.isEmpty());
        }

返回遍历元素
有修改抛出异常；在数组范围内，直接返回，并把指针向后移动；如果数组遍历完，就遍历双端队列。
从这里其实可以看出来，用迭代器遍历元素的时候，用下标cursor来进行数组遍历的，设计返回的结果并不会是一个有序的序列。

  public E next() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
                //有修改抛出异常
                //在数组范围内，直接返回，并把指针向后移动
            if (cursor < size)
                return (E) queue[lastRet = cursor++];
                //如果数组遍历完，就遍历双端队列
            if (forgetMeNot != null) {
                lastRet = -1;
                lastRetElt = forgetMeNot.poll();
                if (lastRetElt != null)
                    return lastRetElt;
            }
            throw new NoSuchElementException();
        }

用迭代器删除元素。
在上面方法中用lastRet记录上一次返回的元素下标。
可以看到，删除时是把上一次访问的元素删除掉，调用的是队列本身的删除方法，会进行内部调整。
如果返回的是null，说明删除的是最后一个元素，把当前指针后移一下。否则，就把删除过的元素保存起来。

        public void remove() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
                //在上面方法中用lastRet记录上一次返回的元素下标。
            if (lastRet != -1) {
            //可以看到，删除时是把上一次访问的元素删除掉，
            //调用的是队列本身的删除方法，会进行内部调整。
                E moved = PriorityQueue.this.removeAt(lastRet);
                //删除完了就置为-1
                lastRet = -1;
                //如果返回的是null，说明删除的是最后一个元素，
                //把当前指针后移一下
                if (moved == null)
                    cursor--;
                else {
                //否则，就把删除过的元素保存起来
                    if (forgetMeNot == null)
                        forgetMeNot = new ArrayDeque<>();
                    forgetMeNot.add(moved);
                }
            } else if (lastRetElt != null) {
            //当下标为-1时，用元素直接删除，可能发生在调用删除之后又删除一次
                PriorityQueue.this.removeEq(lastRetElt);
                lastRetElt = null;
            } else {
                throw new IllegalStateException();
            }
            expectedModCount = modCount;
        }
    }

结论：
优先队列内部实现就是堆排序的算法，不适合做排行。