堆是什么

1.是一种特殊的二叉树（完全二叉树） 2.通过数组的方式顺序存储 3.对于这个数的任意节点来说，满足根节点大于左右子树的值（大堆），或者任意一节点满足根节点的值小于左右子树的值（小堆）

堆能干啥

1.能高效得找出一个集合的最大/最小元素（堆顶元素） 2.能高效得找到前K大/前K小的元素（topk问题）

核心操作

向下调整 & 向上调整

1.向下调整（以大根堆为例）

时间复杂度：O(logN) (size固定，child每次乘以2)

 //按照大堆来实现

    //向下调整

    //size ☞ array中那部分内容为堆 
    //index ☞ 从哪个位置开始向下调整 
    //如果父节点的下标为i，左子树的下标为2*i+1，右子树的下标为2*i+2 
    //子节点的下标为i，父节点的下标为（i-1）/2 
    public static void shiftDown(int[] array, int size, int index){
        int parent = index;
        int child = parent * 2 + 1;
        while (child < size){
            //里面的条件的含义，是看看parent有没有子节点 
            //把左右子树中较大的节点 
            if (child + 1 < size && array[child+1] > array[child]){
                child = child+1;
            }
            //上述完成后，child一定是最大的元素 
            if (array[child] > array[parent]){
                //需要交换 
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            }else {
                //说明当前位置开始已经符合堆的要求了 
                break;
            }
            parent = child;
            child = 2*parent+1;
        }
    }

    public static void createHeap(int[] array, int size){
        //基于向下调整 
        //建堆可以基于向下调整和向上调整 
        //如果是向下调整，就需要从后往前遍历数组 
        for (int i = (size - 1 - 1)/2; i>= 1; i--){
            shiftDown(array,size,i);
        }
    }

    public static void main(String[] args) {
        int[] array = {9,5,2,7,3,6,8};
        createHeap(array,array.length);
        System.out.println(Arrays.toString(array));
    }

2.向上调整

  //向上调整
    
    //此时size这个参数其实不需要用到，判断是否调整完了只需要和0比较就行了

    private int[] array = new int[100];
    private int size = 0;
    public static void shiftUp(int[] array, int size, int index){
        int child = index;
        int parent = (child - 1)/2;
        while (child > 0){
            if (array[parent] < array[child]){
                //当前不符合大堆要求 
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            }else {
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

添加/删除/取堆顶元素

1）添加元素（使用向上调整）

    private int[] array = new int[100];
    private int size = 0;

    public void offer(int x){
        //新加的元素放到了数组的最后，把这个新加的节点就弄成child 
        array[size] = x;
        size++;
        //把新加入的元素进行向上调整 
        shiftUp(array,size - 1);
    }

    public static void shiftUp(int[] array, int index){
        int child = index;
        int parent = (child - 1)/2;
        while (child > 0){
            if (array[parent] < array[child]){
                //当前不符合大堆要求 
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            }else {
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

2）删除元素（使用向下调整）

 public int poll(){
        //下标为0的元素就是队首元素，删掉的同时，剩下的队列也是堆 
        //要删除堆顶元素，直接把数组中的最后一个元素给赋值到堆顶元素 
        //同时 size-- 就把元素删掉了 
        int oldValue = array[0];
        array[0] = array[size-1];
        size--;
        shiftDown(array,size,0);
        return oldValue;
    }
    public static void shiftDown(int[] array, int size, int index){
        int parent = index;
        int child = parent * 2 + 1;
        while (child < size){
            //里面的条件的含义，是看看parent有没有子节点 
            //把左右子树中较大的节点 
            if (child + 1 < size && array[child+1] > array[child]){
                child = child+1;
            }
            //上述完成后，child一定是最大的元素 
            if (array[child] > array[parent]){
                //需要交换 
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            }else {
                //说明当前位置开始已经符合堆的要求了 
                break;
            }
            parent = child;
            child = 2*parent+1;
        }
    }

3）取堆顶元素

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

标准库中的优先队列

import java.util.PriorityQueue;

public class TestPriorityQueue {
    //标准库的优先队列(默认为小堆) 
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(7);
        queue.offer(3);
        queue.offer(6);
        while (!queue.isEmpty()){
            int cur = queue.poll();
            System.out.println(cur);
        }

    }

}