PriorityQueue源码分析

大家好，又见面了，我是你们的朋友全栈君。

来源：
Java编程的逻辑

1 前导

将新的头部与两个孩子节点中较小的比较，如果不大于该孩子节点，则满足堆的性质，结束，否则与较小的孩子进行交换，交换后，再与较小的孩子比较和交换，一直到没有孩子，或者不大于两个孩子节点。这个过程我们般称为siftdown

与父节点比较，如果大于等于父节点，则满足堆的性质，结束，否则与父节点进行交换，然后再与父节点比较和交换，直到父节点为空或者大于等于父节点;称之为siftup

2 实现原理

PriorityQueue是优先级队列，它首先实现了队列接口(Queue)，与LinkedList类似，它的队列长度也没有限制，与一般队列的区别是，它有优先级的概念，每个元素都有优先级，队头的元素永远都是优先级最高的。

PriorityQueue内部是用堆实现的，内部元素不是完全有序的，不过，逐个出队会得到有序的输出。

虽然名字叫优先级队列，但也可以将PriorityQueue看做是一种比较通用的实现了堆的性质的数据结构，可以用PriorityQueue来解决适合用堆解决的问题

2.1 Queue接口

public interface Queue<E> extends Collection<E> { 
   
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

2.2 构造方法

public PriorityQueue() { 
   
    this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity) { 
   
    this(initialCapacity, null);
}

public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) { 
   
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
} 

PriorityQueue是用堆实现的，堆物理上就是数组，与ArrayList类似，PriorityQueue同样使用动态数组，根据元素个数动态扩展，initialCapacity表示初始的数组大小，可以通过参数传入。对于默认构造方法，initialCapacity使用默认值11。对于最后三个构造方法，它们接受一个已有的Collection，数组大小等于参数容器中的元素个数。

与TreeMap/TreeSet类似，为了保持一定顺序，PriorityQueue要求，要么元素实现Comparable接口，要么传递一个比较器Comparator

2.3 内部组成

private transient Object[] queue//实际存储元素的数组
private int size = 0;//当前元素个数
private final Comparator<? super E> comparator;
private transient int modCount = 0;

2.4 入队

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

//如果原长度比较小，扩展为2oldCapacity+2，否则就是增加50%，使用Arrays.copyOf方法拷贝数组
private void grow(int minCapacity) { 
   
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // newCapacity溢出时，就变为Integer.MAX_VALUE或MAX_ARRAY_SIZE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    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;
}

//新元素(x)不断与父节点(e)比较，如果新元素(x)大于等于父节点(e)，则已满足堆的性质，退出循环，k就是新元素最终的位置；
//否则，将父节点往下移(queue[k]=e)，继续向上寻找(k=parent)
private void siftUp(int k, E x) { 
   
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

@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;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

@SuppressWarnings("unchecked")
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;
}

2.5 查看头部元素

public E peek() { 
   
    if (size == 0)
        return null;
    return (E) queue[0];
}

2.6 删除头部元素

//返回结果result为第一个元素，x指向最后一个元素，将最后位置设置为null (queue[s] = null)
//最后调用siftDown将原来的最后元素x插入头部并调整堆
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;
}
//将原来的最后元素x插入头部并调整堆
private void siftDown(int k, E x) { 
   
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

//新元素key不断与较小的孩子比较，如果小于等于较小的孩子，则已满足堆的性质，退出循环，k就是最终位置；
//否则将较小的孩子往上移，继续向下寻找
private void siftDownComparable(int k, E x) { 
   
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        
    while (k < half) { 
   //编号为k的节点有孩子节点，则进入循环
        //表示较小的孩子编号，假定为左孩子，如果有右孩子(编号right)且小于左孩子则child会变为right
        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];//k=child这一步就不用判断，直接赋值为child即可
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;//上移
        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;
}

2.7 查找元素

public boolean contains(Object o) { 
   
    return indexOf(o) != -1;
}

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

2.8 根据值删除元素

//先查找元素的位置i，然后调用removeAt进行删除
public boolean remove(Object o) { 
   
    int i = indexOf(o);
    if (i == -1)
        return false;
    else { 
   
        removeAt(i);
        return true;
    }
}
//如果是删除最后一个位置，直接删即可;
//否则移动最后一个元素moved到位置i并进行堆调整;
//调整有两种情况，如果大于孩子节点，则向下调整，否则如果小于父节点则向上调整
private E removeAt(int i) { 
   
    assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) //删除最后一个位置
        queue[i] = null;
    else { 
   
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);//先向下调整试试
        if (queue[i] == moved) { 
   //如果没有向下调整过
            siftUp(i, moved);//则向上调整试试
            if (queue[i] != moved)//如果向上调整过
                return moved;//则返回moved
        }
    }
    //其他情况返回null，即向下调整过，或没有调整过
    //用于正确实现PriorityQueue迭代器的删除方法
    return null;
}

2.9 构建初始堆

如果从一个既不是PriorityQueue也不是SortedSet的容器构造堆，代码为：

private void initFromCollection(Collection<? extends E> c) { 
   
    initElementsFromCollection(c);
    heapify();
}

//主要是初始化queue和size。
private void initElementsFromCollection(Collection<? extends E> c) { 
   
    Object[] a = c.toArray();
    if (a.getClass() != Object[].class)
        a = Arrays.copyOf(a, a.length, Object[].class);
    this.queue = a;
    this.size = a.length;
}

//从最后一个非叶子节点开始，一直往前直到根;
//对每个节点，执行向下调整siftdown；
//也就是说，自底向上，先使每个最小子树为堆，然后每对左右子树和其父节点合并，调整为更大的堆，因为每个子树已经为堆，所以调整就是对父节点执行siftdown，就这样一直合并调整直到根
private void heapify() { 
   
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}

如果构造方法中的参数是PriorityQueue或SortedSet，则它们的toArray方法返回的数组就是有序的，就满足堆的性质，就不需要执行heapify了。

3 特点分析

PriorityQueue实现了Queue接口，有优先级，内部是用堆实现的，这决定了它有如下特点：

• 实现了优先级队列，最先出队的总是优先级最高的，即排序中的第一个。
• 优先级可以有相同的，内部元素不是完全有序的，如果遍历输出，除了第一个，其他没有特定顺序。
• 查看头部元素的效率很高，为O(1)，入队、出队效率比较高，为O(log2(N))，构建堆heapify的效率为O(N)。
• 根据值查找和删除元素的效率比较低，为O(N)。