优先级队列（堆）

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++;
            }
 
            //如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
            if(array[parent] <= array[child]) {
                break;
            } else {
                //将双亲与较小的孩子交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
 
                //parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = 2 * parent + 1;
            }
        }
    }

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

public void shiftUp(int array[], 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) / 2;
            }
        }
    }

 public static void poll(int[] array, int size) {
        //交换顶和末元素,size为当前数组大小
        int tmp = array[0];
        array[0] = array[--size];
        array[--size] = array[0];
        
        shiftDown(array, array[0]);
    }

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

static class IntCmp implements Comparator<Integer> {
     @Override
     public int compare(Integer o1, Integer o2) {
        return o2 - o1;//这里的比较使最终创建结果为大根堆
     }
}
 
 
 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());
    }

 public 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("优先级队列不为空");
        }
    }

privatestaticfinalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;
 
privatevoidgrow(intminCapacity){
 intoldCapacity=queue.length;
  //Doublesizeifsmall; elsegrowby50%
  intnewCapacity=oldCapacity+((oldCapacity<64)?
                  (oldCapacity+2):
                  (oldCapacity>>1));
  //overflow-consciouscode
  if(newCapacity-MAX_ARRAY_SIZE>0)
    newCapacity=hugeCapacity(minCapacity);
  queue=Arrays.copyOf(queue,newCapacity);
}
 
privatestaticinthugeCapacity(intminCapacity){
 if(minCapacity<0)//overflow
    thrownewOutOfMemoryError();
  return(minCapacity>MAX_ARRAY_SIZE)?
    Integer.MAX_VALUE:
    MAX_ARRAY_SIZE;
}