优先级队列（堆）

 public void shiftDown(int[] array, int parent) {
    // child先标记parent的左孩子，因为parent可能右左没有右
    int child = 2 * parent + 1;
    int size = array.length;
    
    while (child < size) {
        
        // 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
        if(child+1 < size && array[child+1] < array[child]){
            child += 1;
        }
        // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
        if (array[parent] <= array[child]) {
            break;
        }else{
            // 将双亲与较小的孩子交换
            int t = array[parent];
            array[parent] = array[child];
            array[child] = t;
           
            // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
            parent = child;
            child = parent * 2 + 1;
         }
     }
 }

 public static void createHeap(int[] array) {
     // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
     int root = ((array.length-2)>>1);
     for (; root >= 0; root--) {
         shiftDown(array, root);
     }
 }

public void shiftUp(int child) {
    // 找到child的双亲
     int parent = (child - 1) / 2;
    
    while (child > 0) {
        // 如果双亲比孩子大，parent满足堆的性质，调整结束
        if (array[parent] > array[child]) {
            break;
        }
        else{
            // 将双亲与孩子节点进行交换 
            int t = array[parent];
            array[parent] = array[child];
            array[child] = t;
        
            // 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增
            child = parent;
            parent = (child - 1) / 1;
        }
    }
 }

 public class MyPriorityQueue {
    // 演示作用，不再考虑扩容部分的代码
    private int[] array = new int[100];
    private int size = 0;
    
    public void offer(int e) {
        array[size++] = e;
        shiftUp(size - 1);
    }

     public int poll() {
        int oldValue = array[0];
        array[0] = array[--size];
        shiftDown(0);
        return oldValue;
     }

     public int peek() {
     return array[0];
     }
 }

import java.util.PriorityQueue;

 static void TestPriorityQueue(){
        // 创建一个空的优先级队列，底层默认容量是11
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
 
        // 创建一个空的优先级队列，底层的容量为initialCapacity
        PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
 
        ArrayList<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(3);
        list.add(2);
        list.add(1);
 
        // 用ArrayList对象来构造一个优先级队列的对象
        // q3中已经包含了三个元素
        PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
        System.out.println(q3.size());
        System.out.println(q3.peek());
    }

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
 }
 
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
        p.offer(4);
        p.offer(3);
        p.offer(2);
        p.offer(1);
        p.offer(5);
        System.out.println(p.peek());
    }
 }

        System.out.println(p.peek());
    }
 }
 static void TestPriorityQueue2(){
    int[] arr = {4,1,9,2,8,0,7,3,6,5};
 
    // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
    // 否则在插入时需要不多的扩容
    // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
    PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
    for (int e: arr) {
        q.offer(e);
    }
 
    System.out.println(q.size());   // 打印优先级队列中有效元素个数
    System.out.println(q.peek());   // 获取优先级最高的元素
 
    // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
    q.poll();
    q.poll();
    System.out.println(q.size());   // 打印优先级队列中有效元素个数
    System.out.println(q.peek());   // 获取优先级最高的元素
 
    q.offer(0);
    System.out.println(q.peek());   // 获取优先级最高的元素
 
    // 将优先级队列中的有效元素删除掉，检测其是否为空
    q.clear();
    if(q.isEmpty()){
        System.out.println("优先级队列已经为空!!!");
    }
    else{
        System.out.println("优先级队列不为空");
    }
 }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
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 int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
 }