public class PriorityQueue<E> 
        extends AbstractQueue<E>
        implements java.io.Serializable {

    /**
     * 數(shù)組初始容量大小
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * 數(shù)組，用于存儲(chǔ)元素
     */
    transient Object[] queue; // non-private to simplify nested class access

    /**
     * 元素個(gè)數(shù)
     */
    private int size = 0;

    /**
     * 比較器，用于排序元素優(yōu)先級(jí)
     */
    private final Comparator<? super E> comparator;

}

/**
 * 無參構(gòu)造方法
 */
PriorityQueue<Integer> blockingQueue1 = new PriorityQueue<>();

/**
 * 指定容量大小的構(gòu)造方法
 */
PriorityQueue<Integer> blockingQueue2 = new PriorityQueue<>(10);

/**
 * 指定比較器的有參構(gòu)造方法
 */
PriorityQueue<Integer> blockingQueue3 = new PriorityQueue<>(Integer::compareTo);

/**
 * 同時(shí)指定容量和比較器的有參構(gòu)造方法
 */
PriorityQueue<Integer> blockingQueue4 = new PriorityQueue<>(10, Integer::compare);

/**
 * 無參構(gòu)造方法
 */
public PriorityQueue() {
    // 使用默認(rèn)容量大小11，不指定比較器
    this(DEFAULT_INITIAL_CAPACITY, null);
}

/**
 * 指定容量大小的構(gòu)造方法
 */
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

/**
 * 指定比較器的有參構(gòu)造方法
 */
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

/**
 * 同時(shí)指定容量和比較器的有參構(gòu)造方法
 */
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
    if (initialCapacity < 1) {
        throw new IllegalArgumentException();
    }
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

/**
 * offer方法入口
 *
 * @param e 元素
 * @return 是否插入成功
 */
public boolean offer(E e) {
    // 1. 判空，傳參不允許為null
    if (e == null) {
        throw new NullPointerException();
    }
    modCount++;
    int i = size;
    // 2. 當(dāng)數(shù)組滿的時(shí)候，執(zhí)行擴(kuò)容
    if (i >= queue.length) {
        grow(i + 1);
    }
    size = i + 1;
    // 3. 如果是第一次插入，就直接把元素插入到數(shù)組頭部
    if (i == 0) {
        queue[0] = e;
    } else {
        // 4. 如果不是第一次插入，就找個(gè)合適的位置插入（需要保證插入后數(shù)組有序）
        siftUp(i, e);
    }
    return true;
}

/**
 * 擴(kuò)容
 */
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 1. 如果原數(shù)組容量小于64，就執(zhí)行2倍擴(kuò)容，否則執(zhí)行1.5擴(kuò)容
    int newCapacity = oldCapacity + 
            ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
    // 2. 校驗(yàn)最大容量不能超過Integer最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }
    // 3. 直接擴(kuò)容后新數(shù)組賦值給原數(shù)組
    queue = Arrays.copyOf(queue, newCapacity);
}

// 把元素插入到合適的位置
private void siftUp(int k, E x) {
    // 1. 如果初始化的時(shí)候，自定義了比較器，就使用自定義比較器的插入方法，否則使用默認(rèn)的。
    if (comparator != null) {
        siftUpUsingComparator(k, x);
    } else {
        siftUpComparable(k, x);
    }
}

// 自定義比較器的插入方法
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        // 1. 找到父節(jié)點(diǎn)
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        // 2. 如果當(dāng)前節(jié)點(diǎn)元素比父節(jié)點(diǎn)的元素小，就把父節(jié)點(diǎn)元素向下移動(dòng)（給當(dāng)前元素騰出位置）
        if (comparator.compare(x, (E) e) >= 0) {
            break;
        }
        queue[k] = e;
        k = parent;
    }
    // 3. 把當(dāng)前元素插入到父節(jié)點(diǎn)的位置
    queue[k] = x;
}

// 默認(rèn)的插入方法
private void siftUpComparable(int k, E x) {
    // 1. 使用默認(rèn)比較器
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        // 2. 找到父節(jié)點(diǎn)
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        // 3. 如果當(dāng)前節(jié)點(diǎn)元素比父節(jié)點(diǎn)的元素小，就把父節(jié)點(diǎn)元素向下移動(dòng)（給當(dāng)前元素騰出位置）
        if (key.compareTo((E) e) >= 0) {
            break;
        }
        queue[k] = e;
        k = parent;
    }
    // 4. 把當(dāng)前元素插入到父節(jié)點(diǎn)的位置
    queue[k] = key;
}

/**
 * add方法入口
 *
 * @param e 元素
 * @return 是否添加成功
 */
public boolean add(E e) {
    return offer(e);
}

/**
 * poll方法入口
 */
public E poll() {
    // 1. 如果數(shù)組為空，返回null
    if (size == 0) {
        return null;
    }
    int s = --size;
    modCount++;
    // 2. 暫存數(shù)組頭節(jié)點(diǎn)，最后返回
    E result = (E) queue[0];
    // 3. 暫存數(shù)組尾節(jié)點(diǎn)，調(diào)整最小堆的時(shí)候，需要上移
    E x = (E) queue[s];
    // 4. 刪除尾節(jié)點(diǎn)
    queue[s] = null;
    // 5. 調(diào)整最小堆
    if (s != 0) {
        siftDown(0, x);
    }
    return result;
}

/**
 * remove方法入口
 */
public E remove() {
    // 1. 直接調(diào)用poll方法
    E x = poll();
    // 2. 如果取到數(shù)據(jù)，直接返回，否則拋出異常
    if (x != null) {
        return x;
    } else {
        throw new NoSuchElementException();
    }
}

/**
 * peek方法入口
 */
public E peek() {
    // 返回?cái)?shù)組頭節(jié)點(diǎn)
    return (size == 0) ? null : (E) queue[0];
}

/**
 * element方法入口
 */
public E element() {
    // 1. 調(diào)用peek方法查詢數(shù)據(jù)
    E x = peek();
    // 2. 如果查到數(shù)據(jù)，直接返回
    if (x != null) {
        return x;
    } else {
        // 3. 如果沒找到，則拋出異常
        throw new NoSuchElementException();
    }
}