堆的基本概念

 //按照大堆来实现

    //向下调整

    //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));
    }

  //向上调整
    
    //此时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;
        }
    }

    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;
        }
    }

 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;
        }
    }

 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);
        }

    }

}