《优先队列 PriorityQueue》

import java.util.Arrays;

/**
 * 优先队列
 * 优先队列是一个基于优先级堆的无界队列。优先队列的元素按照其自然顺序进行排序
 */
public class PriorityQueue<E extends Comparable<? super E>> implements Queue<E> {

    /**
     * 要分配的数组的最大大小。
     * 一些虚拟机在数组中保留一些头字。尝试分配更大的数组可能会导致 OutOfMemoryError：
     * 请求的数组大小超出 VM 限制
     */
    public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

    /**
     * 默认初始容量
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    transient Object[] elements;

    int size;

    /**
     * 构造一个空优先队列，其初始容量足以容纳 11 个元素。
     */
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    /**
     * 构造一个具有指定初始容量的优先队列。
     *
     * @param initialCapacity 优先队列的初始容量
     * @throws IllegalArgumentException 如果指定的初始容量为负
     */
    public PriorityQueue(int initialCapacity) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.elements = new Object[initialCapacity];
    }

    /**
     * 将一个数组堆化处理
     *
     * @param nums 带堆化的数组
     */

    public PriorityQueue(E[] nums) {
        initFromArray(nums);
    }

    // Ensures that elementData[0] exists, helping peek() and poll().
    private static Object[] ensureNonEmpty(Object[] nums) {
        return (nums.length > 0) ? nums : new Object[1];
    }

    /**
     * 在位置 k 处插入项 x，通过将 x 沿着树重复降级直到它小于或等于其子项或者是叶子来保持堆不变性。
     */
    @SuppressWarnings("unchecked")
    private static <E> void siftDownComparable(int index, Object element, Object[] elements, int length) {
        int half = length >>> 1;
        Comparable<? super E> key = (Comparable<? super E>) element;
        while (index < half) {

            int child = leftChild(index);

            // 两个孩子中的较小者
            Object c = elements[child];

            // 右边孩子节点
            int rightChildIndex = child + 1;

            if (rightChildIndex < length &&
                    ((Comparable<? super E>) c).compareTo((E) elements[rightChildIndex]) > 0) {
                c = elements[child = rightChildIndex];
            }

            // key小于两个孩子节点 满足堆的性质
            if (key.compareTo((E) c) <= 0)
                break;

            elements[index] = c;
            index = child;
        }
        elements[index] = key;
    }

    /**
     * 左孩子节点
     *
     * @param parent 父节点
     * @return 左孩子节点
     */
    private static int leftChild(int parent) {
        return parent << 1 + 1;
    }

    @SuppressWarnings("unchecked")
    private static <T> void siftUpComparable(int index, T element, Object[] elements) {
        Comparable<? super T> key = (Comparable<? super T>) element;
        while (index > 0) {
            int parent = parent(index);
            Object e = elements[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            elements[index] = e;
            index = parent;
        }
        elements[index] = key;
    }

    /**
     * 父节点
     *
     * @param index 子节点
     * @return 父节点
     */
    private static int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent");
        }
        return (index - 1) >>> 1;
    }

    /**
     * 返回一个新的数组长度，以便将其传递给 Arrays.copyOf 方法。
     * 该长度应该是新数组的长度。
     * 该方法将计算新数组的长度，以便将其传递给 Arrays.copyOf 方法。
     * 该长度应该是新数组的长度。
     * 该方法将计算新数组的长度，以便将其传递给 Arrays.copyOf 方法。
     * 如果新长度不超过 MAX_ARRAY_LENGTH，则它将是新数组的长度。
     * 否则，如果旧长度小于 MAX_ARRAY_LENGTH，则新长度将是 MAX_ARRAY_LENGTH。
     * 否则，新长度将是 Integer.MAX_VALUE。
     * 参数：
     * oldLength - 旧数组的长度
     * minGrowth - 最小增长
     * prefGrowth - 首选增长
     * 返回：
     * 新数组的长度
     */
    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0

        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }

    /**
     * 边缘条件的容量计算，特别是溢出。
     * 参数：
     * oldLength - 旧数组的长度
     * minGrowth - 最小增长
     * 返回：
     * 新数组的长度
     * 抛出：
     * OutOfMemoryError - 如果新长度超出范围
     */

    private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError(
                    "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            return minLength;
        }
    }

    /**
     * 初始化堆的内存
     *
     * @param nums 初始化传入的树组
     */

    private void initFromArray(E[] nums) {
        initElementsFromArray(nums);
        heapify();
    }


    /**
     * 初始化堆的内存
     *
     * @param nums 初始化传入的树组
     */
    private void initElementsFromArray(E[] nums) {
        int len = nums.length;
        for (Object e : nums)
            if (e == null)
                throw new NullPointerException();
        // 确保已经初始化
        this.elements = ensureNonEmpty(nums);
        this.size = len;
    }

    /**
     * Establishes the heap
     */
    private void heapify() {
        final Object[] es = elements;
        // 容量
        int n = size;
        // 最后一个非叶子节点
        int i = (n >>> 1) - 1;
        for (; i >= 0; i--)
            siftDownComparable(i, es[i], es, n);
    }

    /**
     * 返回队列中的元素数。
     *
     * @return 队列中的元素数
     */
    @Override
    public int size() {
        return this.size;
    }

    /**
     * 返回队列中的元素数。
     *
     * @return 队列中的元素数
     */
    @Override
    public boolean empty() {
        return size() == 0;
    }

    /**
     * 添加元素
     *
     * @param e 要添加的元素
     * @return 如果队列由于调整大小而更改，则为 true
     * @throws NullPointerException 如果指定的元素为 null
     */
    @Override
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        int i = size;
        if (i >= elements.length)
            grow(i + 1);
        siftUp(i, e);
        size = i + 1;
        return true;
    }

    /**
     * 上浮操作
     * 在位置 k 处插入项 x，通过将 x 沿树向上提升直到它大于或等于其父项，或者是根，来保持堆不变性。
     * 与 siftDown 类似
     */
    private void siftUp(int k, E x) {
        siftUpComparable(k, x, elements);
    }

    /**
     * Increases the capacity of the array.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = elements.length;
        // Double size if small; else grow by 50%
        int newCapacity = newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                /* preferred growth */);
        elements = Arrays.copyOf(elements, newCapacity);
    }

    /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException   if the specified element cannot be
     *                              compared with elements currently in this priority queue
     *                              according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    @Override
    public E poll() {
        final Object[] es;
        final E result;

        if ((result = (E) ((es = elements)[0])) != null) {
            final int n;
            final E x = (E) es[(n = --size)];
            es[n] = null;
            if (n > 0) {
                siftDownComparable(0, x, es, n);
            }
        }
        return result;
    }

    /**
     * Retrieves, but does not remove, the head of this queue.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    @Override
    public E peek() {
        return (E) elements[0];
    }
}