PriorityQueue源码

对于PriorityQueue优先队列最核心的就是其添加元素删除元素后维持元素的顺序的逻辑，其实用的算法其实就是堆排序。堆其实是一种特殊的树，堆是一颗完全二叉树，且堆树又分为大顶堆和小顶堆。

数组是完全二叉树最佳存储结构，因为完全二叉树有特殊的属性，可直接利用数组下标表示左右节点，数组下标为K的元素对应的完全二叉树中左右子节点在数组中的位置分别为2*K + 1、2*K+2。

不论大顶堆还是小顶堆，都是从完全二叉数中最后一个元素的父节点开始堆化，将最大或最小的元素排到堆顶，然后遍历整棵树，每一次将堆顶的元素，和未排序的最后一个元素交换，再进行一次堆化，这样就将数据排好序了。

public class HeapSort {
    public void heapSortAsc(Integer[] arr) {
        int len = arr.length;
        // len / 2 - 1表示的是从完全二叉数中最后一个元素的父节点开始堆化
        for (int start = len / 2 - 1; start >= 0; start--) {
            maxHeapDown(arr, start, len);  // 将树中最大的元素排到堆顶
        }
        // 上面的循环只是将最大的元素排到了堆顶，但是整棵树即数组中的元素不是有序的
        // 每一次将对顶的元素即最大的元素，和未排序的最后一个元素交换，再进行一次堆化，这样就将数据从小到大排序了
        for (int index = len - 1; index > 0; index--) {
            int temp = arr[0];
            arr[0] = arr[index];
            arr[index] = temp;
            maxHeapDown(arr, 0, index); // len~i已经排好序了
        }
    }
    /**
     * 将完全二叉树中最大的元素放到堆顶，end表示最多建到的点
     */
    public void maxHeapDown(Integer[] arr, int start, int end) {
        int parent = start;
        int left = parent * 2 + 1; // 找到当前节点的左子节点位置
        while (left < end) {
            int max = left; // max表示左右节点大的那一个在数组中的位置
            if (left + 1 < end && arr[left] < arr[left + 1]) { // 比较左右节点和父节点的大小
                max = left + 1; // 若右节点比左节点大，则将父节点和右节点交换
            }
            // 若左节点比右节点大，则将父节点和左节点交换
            if (arr[parent] > arr[max]) { // 若父节点大于子节点中最大的那一个，则退出
                return;
            } else { // 若父节点小于子节点中最大的那一个，则交换
                int tmp = arr[parent];
                arr[parent] = arr[max];
                arr[max] = tmp;
                parent = max;   // 还原指针，交换数据后，max指向的是被交换下来的父节点，还需要往下遍历，故需要将parent指向需要遍历的数据
                left = parent * 2 + 1;  // 找到之前左右节点大的节点的左子节点在数组中的索引位置
            }
        }
    }
    public void heapSortDesc(Integer[] arr) {
        int len = arr.length;
        for (int start = len / 2 - 1; start >= 0; start--) {
            minHeapDown(arr, start, len);
        }

        for (int index = len - 1; index > 0; index--) {
            int tmp = arr[0];
            arr[0] = arr[index];
            arr[index] = tmp;
            minHeapDown(arr, 0, index);
        }
    }
   /**
     * 将完全二叉树中最小的元素放到堆顶，end表示最多建到的点
     */
    public void minHeapDown(Integer[] arr, int start, int end) {
        int parent = start;
        int left = 2 * start + 1; // 找到当前节点的左子节点位置
        while (left < end) {
            int min = left; // min表示左右节点小的那一个在数组中的位置
            if (left + 1 < end && arr[left] > arr[left + 1]) {
                min = left + 1;
            }
            if (arr[min] > arr[parent]) {  // 比较左右节点中小的那一个和父节点的大小
                break;  // 若小的那个节点都比父节点大，说明不需要再遍历了
            }
            int tmp = arr[min];
            arr[min] = arr[parent];
            arr[parent] = tmp;
            parent = min;   // 还原指针，交换数据后，min指向的是被交换下来的父节点，还需要往下遍历，故需要将parent指向需要遍历的数据
            left = 2 * parent + 1;  // 找到之前左右节点小的节点的左子节点在数组中的索引位置
        }
    }
    @Test
    public void InsertSortTest() {
        {
            Integer[] arr = new Integer[]{8, 6, 4, 9, 74, 25, 1, 3, 5, 28, 35, 0, 22, 2, 7, 10, 26, 29};
            heapSortAsc(arr);
            System.err.println(" after:" + Arrays.asList(arr));
        }
        {
            Integer[] arr = new Integer[]{8, 6, 4, 9, 74, 25, 1, 3, 5, 28, 35, 0, 22, 2, 7, 10, 26, 29};
            heapSortDesc(arr);
            System.err.println(" after:" + Arrays.asList(arr));
        }
    }
}

若传入的集合是一个排序好的集合，则直接将数据拷贝到PriorityQueue的内部数组queue中，若传入结合本身就是一个PriorityQueue，则直接赋值queue。

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    transient Object[] queue;
    private int size = 0;
    private final Comparator<? super E> comparator;
    public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss); // 直接将数据拷贝到queue中
        }
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }
    private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        // If c.toArray incorrectly doesn't return Object[], copy it.
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null)
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }
    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            initFromCollection(c);
        }
    }
}

堆化的关键代码，和上面的堆排序的例子一样，这里是使用的小顶堆

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}
private void heapify() {
    // 从完全二叉数中最后一个元素的父节点开始堆化，之所以右移再减一，是因为数组下标是从0开始的
    for (int i = (size >>> 1) - 1; i >= 0; i--) 
        siftDown(i, (E) queue[i]);
}
private void siftDown(int k, E x) {
    if (comparator != null)	// 若传入的comparator不为空则使用传入的
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) { // 传入的K必须要小于堆元素个数的一半，因为堆化最多就循环half次
        int child = (k << 1) + 1; 	// 找到K节点的左子节点
        Object c = queue[child];	// 获取K节点的左子节点值
        int right = child + 1;		// 找到K节点的右子节点
        if (right < size && comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right]; // 若K的左子节点值小于右子节点值，则将C置为右子节点的值
        if (comparator.compare(x, (E) c) <= 0)	// 将目标对象X与K的左右子节点中最小的比较
            break; 		// 若目标对象X比K的左右子节点最小的值还小，则不用交换直接退出
        queue[k] = c; 	// 若X比K的左右子节点最小的值还大，则将K对应的值与子节点中最小的值交换
        k = child; 		// 将K指针恢复，因为上一步做了交换，K指向的交换后的c
    }
    queue[k] = x; 		// 将目标值赋值给K
}
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) { // 传入的K必须要小于堆元素个数的一半，因为堆化最多就循环half次
        int child = (k << 1) + 1; 	// 找到K节点的左子节点
        Object c = queue[child];	// 获取K节点的左子节点值
        int right = child + 1;		// 找到K节点的右子节点
        if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right]; 	// 若K的左子节点值小于右子节点值，则将C置为右子节点的值
        if (key.compareTo((E) c) <= 0)	// 将目标对象X与K的左右子节点中最小的比较
            break;		// 若目标对象X比K的左右子节点最小的值还小，则不用交换直接退出
        queue[k] = c;	// 若X比K的左右子节点最小的值还大，则将K对应的值与子节点中最小的值交换
        k = child;	// 将K指针恢复，因为上一步做了交换，K指向的交换后的c
    }
    queue[k] = key;	// 将目标值赋值给K
}

添加元素，若元素个数已经大于等于数组长度了，则进行扩容，若旧的容量小于64，则每次扩容为旧容量的一倍加2，否则扩容旧容量的一半。然后siftUp进行小顶堆插入

public boolean add(E e) {
    return offer(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;
}
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));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
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;	// 找到K的父节点
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;	// 若父节点值小于目标节点直接退出循环，将目标值直接复制给K
        queue[k] = e;	// 若父节点值大于目标节点，则交换父子节点的额值
        k = parent;
    }
    queue[k] = x;
}

删除元素，若队列中无元素则直接返回null，然后获取第0个元素和最后一个元素，然后删除最后一个元素，这里其实就是删除第0个元素，然后将最后一个元素与第0个元素交换，然后再进行一次堆化。

public E poll() {
    if (size == 0) // 若队列元素为null直接返回null
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0]; // 获取第0个元素
    E x = (E) queue[s]; // 获取最后一个元素
    queue[s] = null;// 将最后一个元素置空
    if (s != 0)
        siftDown(0, x);
    return result;
}
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) { // 传入的K必须要小于堆元素个数的一半，因为堆化最多就循环half次
        int child = (k << 1) + 1; 	// 找到K节点的左子节点
        Object c = queue[child];	// 获取K节点的左子节点值
        int right = child + 1;		// 找到K节点的右子节点
        if (right < size && comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right]; // 若K的左子节点值小于右子节点值，则将C置为右子节点的值
        if (comparator.compare(x, (E) c) <= 0)	// 将目标对象X与K的左右子节点中最小的比较
            break; 		// 若目标对象X比K的左右子节点最小的值还小，则不用交换直接退出
        queue[k] = c; 	// 若X比K的左右子节点最小的值还大，则将K对应的值与子节点中最小的值交换
        k = child; 		// 将K指针恢复，因为上一步做了交换，K指向的交换后的c
    }
    queue[k] = x; 		// 将目标值赋值给K
}