优先级队列
    PriorityBlockingQueue（线程安全）/priorityQueue（非线程安全）
    内部维护了一个数组，初始容量是11
    小顶堆：
    入队的时候向上浮（入队的时候先把元素放到最后，然后向上浮）
    出队向下沉（出队的时候吧最后一个元素放到出队元素的地方然后向下沉）

    数组的第一个元素为空目的就是快速根据子节点找到父节点的位置 index/2 向下取整 = 父节点下标
    image.png
    可以进行排序

    1.     @Test
    2.     public void test5(){
    3.         int[] arr = {3,2,5,8,1,9};
    5.         PriorityQueue<Integer> priorityQueue = new PriorityQueue(arr.length);
    6.         for(int i : arr){
    7.             priorityQueue.add(i);
    8.         }
    9.         Iterator iterator = priorityQueue.iterator();
    10.         while (iterator.hasNext()){
    11.             System.out.print(iterator.next() + ",");
    12.         }
    13.         // 输出：1,2,5,8,3,9, 迭代器没有顺序
    15.         int size = priorityQueue.size();
    16.         for (int i = 0; i < size; i++) {
    17.             System.out.print(priorityQueue.poll() + ",");
    18.         }
    19.         // 输出：1,2,3,5,8,9, poll是有顺序的
    20.     }

    入队：

    1.     public boolean offer(E e) {
    2.         if (e == null)
    3.             throw new NullPointerException();
    4.         final ReentrantLock lock = this.lock;
    5.         lock.lock();
    6.         int n, cap;
    7.         Object[] array;
    8.         while ((n = size) >= (cap = (array = queue).length))
    9.             // 这里执行扩容的方法，使用的cas,因为已进入方法就吧锁释放了
    10.             tryGrow(array, cap);
    11.         try {
    12.             Comparator<? super E> cmp = comparator;
    13.             if (cmp == null)
    14.                 siftUpComparable(n, e, array);
    15.             else
    16.                 siftUpUsingComparator(n, e, array, cmp);
    17.             size = n + 1;
    18.             notEmpty.signal();
    19.         } finally {
    20.             lock.unlock();
    21.         }
    22.         return true;
    23.     }
    26.     private void tryGrow(Object[] array, int oldCap) {
    27.         // 这里释放锁的原因是不阻塞读
    28.         lock.unlock(); // must release and then re-acquire main lock
    29.         Object[] newArray = null;
    30.         // 只需要一个线程做扩容
    31.         if (allocationSpinLock == 0 &&
    32.             UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,
    33.                                      0, 1)) {
    34.             try {
    35.                 int newCap = oldCap + ((oldCap < 64) ?
    36.                                        (oldCap + 2) : // grow faster if small
    37.                                        (oldCap >> 1));
    38.                 if (newCap - MAX_ARRAY_SIZE > 0) {    // possible overflow
    39.                     int minCap = oldCap + 1;
    40.                     if (minCap < 0 || minCap > MAX_ARRAY_SIZE)
    41.                         throw new OutOfMemoryError();
    42.                     newCap = MAX_ARRAY_SIZE;
    43.                 }
    44.                 if (newCap > oldCap && queue == array)
    45.                     newArray = new Object[newCap];
    46.             } finally {
    47.                 allocationSpinLock = 0;
    48.             }
    49.         }
    50.            // 让扩容后的线程优先拿到资源
    51.         if (newArray == null) // back off if another thread is allocating
    52.             Thread.yield();
    53.         lock.lock();
    54.         if (newArray != null && queue == array) {
    55.             queue = newArray;
    56.             System.arraycopy(array, 0, newArray, 0, oldCap);
    57.         }
    58.     }

    DelayQueue 延迟队列
    具有阻塞的功能，线程安全

    1. // 创建一个延迟线程池里面是通过它的内部类DelayedWorkQueue来做的延迟功能，但是原理和DelayQueue差不多
    2. ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(10);
    5.     public ScheduledThreadPoolExecutor(int corePoolSize) {
    6.         super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,
    7.               new DelayedWorkQueue());
    8.     }
    1.     private final transient ReentrantLock lock = new ReentrantLock();
    2.     // 内部调用的就是优先级队列的方法
    3.     private final PriorityQueue<E> q = new PriorityQueue<E>();
    4.     // 当前是否有线程再排队，用于取元素的时候，当取得时候发现有线程在排队那就不用取了，直接排         //队就好了
    5.     private Thread leader = null;
    6.     private final Condition available = lock.newCondition();
    1.     public boolean offer(E e) {
    2.         final ReentrantLock lock = this.lock;
    3.         lock.lock();
    4.         try {
    5.             // 入队直接调用PriorityQueue的offer方法
    6.             q.offer(e);
    7.             if (q.peek() == e) {
    8.                 leader = null;
    9.                 available.signal();
    10.             }
    11.             return true;
    12.         } finally {
    13.             lock.unlock();
    14.         }
    15.     }