前言

主要分析offer(E e) 和 poll() 两个方法，即队列的入队和出队，底层原理是堆排序的上浮和下沉

一、offer(E e)

offer(E e)源码：

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        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函数，代码如下
注意下i，i的含义为新增元素预插入位置的索引，其值为队列的size，即元素e预插入位置为队列尾部

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

siftUpUsingComparator和siftUpComparable逻辑一样
siftUpUsingComparator用自定义比较器来比较元素大小，主要应用于自定义对象
siftUpComparable主要应用于基本数据类型
这里我们主要看下siftUpComparable的实现，源码如下

    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1; // 父节点索引。完全二叉树父子几点的索引关系为: 左子节点索引 = 父节点所以 * 2 + 1
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

代码的逻辑大概是：

方法入参：k表示新增元素x的预插入位置，k的初始值为队列size，x的初始值为要插入的元素
比较新增元素x和其父节点queue[parent]的大小。新增元素的预插入位置索引为k
如果 x >= queue[parent], 由于是最小堆(父节点的值小于子节点)，所以预插入位置正确，执行步骤6
如果 x < queue[parent], 由于是最小堆(父节点的值小于子节点)，所以预插入位置不对，需要调整预插入位置，元素x上浮
简单的说，父节点元素queue[parent]和x交换位置
x交换位置后，不一定比其新父节点元素大，所以需要再次判断、调整。将预插入位置k调整为parent。如果k = 0 , 说明上浮到根节点了，执行步骤6；则重复步骤1
找到了合适的插入位置k，直接赋值：queue[k] = x

二、poll()

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;
    }

重点关注siftDown

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

分析siftDownComparable

    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; // 左子节点索引
            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 = child;
        }
        queue[k] = key;
    }

说明：poll函数弹出的是根节点，调整策略是：预设用最后一个节点填补根节点，然后进行下沉调整
代码的逻辑大概是：

方法入参：k表示新增元素x的预插入位置，k的初始值为0，x的初始值为队尾元素
比较k位置的左右子节点大小。child记录较小节点的索引，c记录较小节点的值
如果x <= c，由于是最小堆(父节点的值小于子节点)，表示预插入位置正确，执行步骤5
如果x > c，把child位置的值(当前比较的3个元素最小的值)赋值给queue(k)(k为当前3个参与比较元素的根节点)，同时更新k的值为child。如果k >= half，说明。。。，执行步骤5；否则执行步骤2
找到了合适的插入位置k，直接赋值：queue[k] = x