📚 目录

• 1. 优先级队列的概念

• 2. 大小根堆的概念以及创建

• 3. 优先级队列基础方法

• 4. 代码汇总

前言：
  在我们日常开发和算法刷题中，经常会遇到这样的场景： 需要动态地从一组数据中，快速取出优先级最高（或最低）的元素。 普通队列的“先进先出”规则已经无法满足需求，这时，优先级队列（PriorityQueue） 就成了我们的最佳选择。

1. 优先级队列的概念

  之前我们学的队列是以：先进先出的的一种数据结构，但是在我们日常开发的过程中有些数据是带有优先级的。
  就好比我们生活中：重伤、急症、老人孕妇优先级更高，不用排队直接先安排就诊；外卖小哥送单：距离近、超时快、顾客催单的 优先级高平台优先先派送这些订单，不是按下单先后。
  JDK1.8中PriorityQueue的底层结构使用了堆这种数据结构，而堆实际上就是在二叉树以层序遍历的方式进行了调整。

---

2. 大小根堆的概念以及创建

  了解完优先级队列的基本概念之后，我们首先得知道优先级队列中堆的概念。
  堆：我们可以理解为将一个完全二叉树以层序遍历的方式放入到当前的数组中。而存储的时候又是按照大根堆或者小根堆的方式进行存储。
  首先我们先给定一个数组，里面存储了6个数字。

大根堆：
  我们前面知道优先级队列存储的方式是二叉树的以层序遍历的方式进行存入到一个数组中。
  此时并没有进行以大堆的方式进行放入到完全二叉树当中。

  以大堆的方式进行存储:
  大堆存储：当前节点的值比它的左右孩子的值要大。

以小堆的方式进行存储：
  小堆存储：当前节点比左右值比它左右孩子的值要小。

---

3. 优先级队列基础方法

建堆

前置条件：

public class MyPriorityQueue {
    public int[] elem;//创建一个存储的数组
    public int useSize;//真实存储的大小
    public MyPriorityQueue() {
        this.elem = new int[10];//默认大小为10，具体大小可根据自己定义。
    }
}    

  创建大堆：

    //创建大根堆
    public void createQueue() {
        //拿到最后一个节点的父节点，每次让父节点移动位置
        for (int parent = (useSize-1-1)/2; parent >=0; parent--) {
            siftDown(parent,useSize);//循环创建大根堆
        }
    }

    //向下调整
    private void siftDown(int parent, int useSize) {
        //首先拿到孩子节点
        int child = 2*parent+1;//拿到最后一个节点的左孩子
        while (child<useSize){
            //此时就需要进行交换了
            //找出左孩子和右孩子的最大值/最小值
            if(child+1<useSize&&elem[child]<elem[child+1]) {
                child++;//只要有右节点并且是左孩子和右孩子中最大的就让child++
            }
            //再让当前的child和parent进行相比较
            if(elem[child]>elem[parent]) {
                //交换完当前一个根的地方
                swap(child,parent,elem);
                //然后我们需要再进行判断当前根的下面是否满足大堆根
                //让parent移动到child
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

交换：

    private void swap(int child, int parent, int[] elem) {
        int tmp = elem[child];//基本的交换方式
        elem[child] = elem[parent];
        elem[parent] = tmp;
    }

  结果：

插入

  为什么是向上调整？
  因为此时我们只需要和parent节点进行判断。

    //插入
    public void offer(int val) {
        //判断是否满
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);//二倍扩容
        }
        elem[useSize] = val;
        useSize++;
        //然后这个时候需要向上调整，拿到最后一个节点
        siftUp(useSize-1);//直接穿最后一个节点进去
    }
    //判断当前优先级队列是否满
    public boolean isFull() {
        return useSize == elem.length;
    }

    //向上调整
    private void siftUp(int child) {
        int parent = (child-1)/2;
        while (child>0) {
            if(elem[child]>elem[parent]) {//和根节点比较
                swap(child,parent,elem);//大于交换
                child = parent;//然后让child往上走
                parent = (child-1)/2;//parent也往上走
            }else {
                break;
            }
        }
    }

结果：

删除

  判断当前优先级队列是否满：

    public boolean isEmpty() {
        return useSize == 0;
    }

 //删除
    public void pollHeap() {
        if(isEmpty()) {//判断优先级队列是否满
            return;
        }
        swap(useSize-1,0,elem);//交换第一个和最后一个元素
        //让useSize--
        useSize--;//有效长度-1
        //进行从新向上调整，调整当前优先级队列的顺序
        siftDown(0,useSize);
        elem[useSize] = 0;//如果为泛型则置为null即可。
    }

  结果：

获取优先级队列栈顶元素

  获取栈顶元素就比较简单了，直接返回0下标的值好了。

    //获取栈顶元素
    public int peekHeap() {
        if(useSize==0) {
            return -1;
        }
        return elem[0];
    }

---

4. 代码汇总

public class MyPriorityQueue {
    public int[] elem;
    public int useSize;
    public MyPriorityQueue() {
        this.elem = new int[10];
    }

    //此时在外面创建一个数组来进行创建一个大根堆放入到elem中
    public void inti(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            useSize++;
        }
    }
    //创建大根堆
    public void createQueue() {
        //拿到最后一个节点的父节点，每次让父节点移动位置
        for (int parent = (useSize-1-1)/2; parent >=0; parent--) {
            siftDown(parent,useSize);
        }
    }
    //向下调整
    private void siftDown(int parent, int useSize) {
        //首先拿到孩子节点
        int child = 2*parent+1;//拿到最后一个节点的左孩子
        while (child<useSize){
            //此时就需要进行交换了
            //找出左孩子和右孩子的最大值/最小值
            if(child+1<useSize&&elem[child]<elem[child+1]) {
                child++;//只要有右节点并且是左孩子和右孩子中最大的就让child++
            }
            //再让当前的child和parent进行相比较
            if(elem[child]>elem[parent]) {
                //交换完当前一个根的地方
                swap(child,parent,elem);
                //然后我们需要再进行判断当前根的下面是否满足大堆根
                //让parent移动到child
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private void swap(int child, int parent, int[] elem) {
        int tmp = elem[child];
        elem[child] = elem[parent];
        elem[parent] = tmp;
    }


    //插入
    public void offer(int val) {
        //判断是否满
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);//二倍扩容
        }
        elem[useSize] = val;
        useSize++;
        //然后这个时候需要向上调整，拿到最后一个节点
        siftUp(useSize-1);
    }
    public boolean isFull() {
        return useSize == elem.length;
    }

    //向上调整
    private void siftUp(int child) {
        int parent = (child-1)/2;
        while (child>0) {
            if(elem[child]>elem[parent]) {
                swap(child,parent,elem);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    //获取栈顶元素
    public int peekHeap() {
        if(useSize==0) {
            return -1;
        }
        return elem[0];
    }

    //删除
    public void pollHeap() {
        if(isEmpty()) {
            return;
        }
        swap(useSize-1,0,elem);
        //让useSize--
        useSize--;
        //进行从新向上调整，调整当前优先级队列的顺序
        siftDown(0,useSize);
        elem[useSize] = 0;
    }
    public boolean isEmpty() {
        return useSize == 0;
    }
}

---