欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java优先队列源码解析

程序员文章站 2024-03-18 08:28:34
...

昨天做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;
        }
    }

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