美文网首页
Queue完全解析

Queue完全解析

作者: ayagg | 来源:发表于2019-02-20 04:37 被阅读0次

    一 概览

    image.png

    由上图可知,Queue分成只扩展AbstractQueue的,实现BlockingQueue接口的,实现TransferQueue的,实现BlockingDeque的以及实现Deque接口的五类

    二 PriorityQueue

    • siftUp
        /**
         * Inserts item x at position k, maintaining heap invariant by
         * promoting x up the tree until it is greater than or equal to
         * its parent, or is the root.
         *
         * To simplify and speed up coercions and comparisons. the
         * Comparable and Comparator versions are separated into different
         * methods that are otherwise identical. (Similarly for siftDown.)
         *
         * @param k the position to fill
         * @param x the item to insert
         */
     @SuppressWarnings("unchecked")
        private void siftUpComparable(int k, E x) {
            Comparable<? super E> key = (Comparable<? super E>) x;
            while (k > 0) {  
                int parent = (k - 1) >>> 1;    //不像siftDown那样需要考虑找左右 孩子中的最小节点,siftUp只需要比较key跟parent节点即可
                Object e = queue[parent];
                if (key.compareTo((E) e) >= 0)
                    break;
                queue[k] = e;
                k = parent;
            }
            queue[k] = key;
        }
    
    • siftDown
        /**
         * Inserts item x at position k, maintaining heap invariant by
         * demoting x down the tree repeatedly until it is less than or
         * equal to its children or is a leaf.
         *
         * @param k the position to fill
         * @param x the item to insert
         */
        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];    //如果右孩子更小,则将right赋给child,把queue[right]赋给c
                if (key.compareTo((E) c) <= 0) //如果目标节点值小于等于c,则break,否则,继续循环
                    break;
                queue[k] = c;
                k = child;
            }
            queue[k] = key;
        }
    
    • offer
        public boolean offer(E e) {
            if (e == null)
                throw new NullPointerException();
            modCount++;
            int i = size;
            if (i >= queue.length)
                grow(i + 1);    //扩容,与map和list的grow类似
            size = i + 1;
            if (i == 0)
                queue[0] = e;
            else
                siftUp(i, e);
            return true;
        }
    

    offer(E e)方法的实现思路如下:
    1)首先检查要添加的元素e是否为null,如果为null,则抛空指针异常,如果不为null,则进行2
    2)判断数组是否已满,如果已满,则进行扩容,否则将元素加入到数组末尾即可。但是由于这个数组表示的是一个“二叉堆”,因此还需要进行相应的调整操作,使得这个数组在添加元素之后依然保持的是二叉堆的特性。

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

    poll 方法的思想为:取出 queue[0] 元素,然后将 queue[size-1] 插入到 queue[0] , 然后向下沉来保持二叉堆的特性。

    相关文章

      网友评论

          本文标题:Queue完全解析

          本文链接:https://www.haomeiwen.com/subject/qyxqdqtx.html