优先级队列（堆）

堆概念的介绍

在之前的文章中介绍过，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列。

在优先级队列PriorityQueue中，底层使用的是堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。每一个父亲节点都比子节点小称为小根堆，每一个父亲节点都比子节点大称为大根堆，如下图所示

堆的存储方式

在堆的概念中提到，堆是一个完全二叉树，在存储的过程中一般采用顺序存储的方式进行，例如有一个集合为{27,15,19,18,28,34,65,49,25,37}，则在其堆中的存储的逻辑结构为

如上所示，在逻辑上为一个完全二叉树，如要将其调整为小根堆或大根堆（以大根堆为例），可以采用将根节点向上调整的方式

堆的创建

向上过程（以大堆为例）

1.让指针parent标记要调整的节点，指针child标记孩子节点中，大孩子的节点

2.将parent与child进行比较，如果child比parent大，则进行交换

循环如上的过程，完成后则调整为大根堆

代码如下

public class MyBigQueue {
    public int[] elem;          //采用数组的方式调整
    public int usesize;         //标志有效数字

    public MyBigQueue() {
        this.elem = new int[10];    //初试化数组大小为10，后期不够再扩容
    }

    public void initElem(int[] array){          //传一个数组初试化elem,并将elem调整为大根堆
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usesize++;
        }
    }

    public void CreatBigQ(){
        for(int parent=(usesize-1-1)/2;parent>=0;parent--){     //自下而上，确定父亲节点
            shifDown(parent,usesize);                       //将每个父亲节点放入方法中进行至下而上的调整
        }

    }

    public void shifDown(int parent,int end){           //写调整的方法
        int child = parent*2+1;
        while (child<end){                          //孩子节点只要没走到数组的结尾就继续遍历
            if(child+1<usesize&&elem[child]<elem[child+1]){
                child++;                                    //走完这一步，child走到了孩子节点的最大值下
            }
            if(elem[child]>elem[parent]){                   //判断是否需要交换
                swap(child,parent);                 //交换另写一个方法
                parent=child;                       //交换完后，
                child=child*2+1;                    //孩子节点走向孩子节点的左孩子节点
            }else {
                break;
            }
        }


    }
    public void swap(int x,int y){
        int tmp = elem[x];
        elem[x]=elem[y];
        elem[y]=tmp;
    }

在二叉树中，一个节点如果有左孩子节点，则左孩子节点的下标为2*X+1(X为当前节点下标)，所以有上述代码 child=child*2+1;

验证

在传入数组arr后，elem为按顺序方式存储的大根堆

堆的删除

注意：堆的删除一点删除的是堆顶的元素

删除理论如下：

1.将堆顶元素对堆中最后一个元素交换
2.将堆的有效数据减少一个，也就是usesize-1；
3.将堆顶元素进行向下调整

代码如下

    public int poll(){
        int tmp = elem[0];    //保存要删除的头节点

        swap(0,usesize-1);    //将头节点和尾节点交换

        usesize--;            //将有效位数减一位

        shifDown(0,usesize);  //传入头节点，向下调整
        return tmp;
    }

验证

头节点置为末尾，有效位数减1，则再遍历时，遍历不到65，视为删除

堆的插入

插入理论如下：

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2.将最后新插入的节点向上调整，直到满足堆的性质

注意，在之前写的代码中，shifDown是向下调整的方法，向上调整需要要重写

代码如下

 public boolean isFull(){
        return usesize==elem.length;        //当有效位和数组的长度相同时，代表数组满了
    }

    public void offer(int val){
        if(isFull()){                   //判断数组是否满了，如果满了就进行扩容
            this.elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usesize]=val;              //将新插入的数据置为数组最后
        usesize++;                      //有效位加1
        shifUp(usesize-1);          //进行向上调整，传入插入数据的下标，视为孩子节点

    }
    public void shifUp(int child){
        int parent = (child-1)/2;       //根据孩子节点确定父亲节点
        while (child>0){                //孩子节点还大于头节点的时候，就继续遍历
            if(elem[child]>elem[parent]){   //孩子节点的值大于父亲节点的值，就进行交换
                swap(child,parent);
                child=parent;           //将父亲节点给孩子，进行向上调整
                parent=(child-1)/2;     //父亲节点给自己的父亲节点
            }else {
                break;
            }
        }
    }

测试如下

全部的完整代码如下

import java.util.Arrays;

public class MyBigQueue {
    public int[] elem;          //采用数组的方式调整
    public int usesize;         //标志有效数字

    public MyBigQueue() {
        this.elem = new int[10];    //初试化数组大小为10，后期不够再扩容
    }

    public void initElem(int[] array){          //传一个数组初试化elem,并将elem调整为大根堆
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usesize++;
        }
    }

    public void CreatBigQ(){
        for(int parent=(usesize-1-1)/2;parent>=0;parent--){     //自下而上，确定父亲节点
            shifDown(parent,usesize);                       //将每个父亲节点放入方法中进行至下而上的调整
        }

    }

    public void shifDown(int parent,int end){           //写调整的方法
        int child = parent*2+1;
        while (child<end){                          //孩子节点只要没走到数组的结尾就继续遍历
            if(child+1<usesize&&elem[child]<elem[child+1]){
                child++;                                    //走完这一步，child走到了孩子节点的最大值下
            }
            if(elem[child]>elem[parent]){                   //判断是否需要交换
                swap(child,parent);                 //交换另写一个方法
                parent=child;                       //交换完后，
                child=child*2+1;                    //孩子节点走向孩子节点的左孩子节点
            }else {
                break;
            }
        }


    }
    public void swap(int x,int y){
        int tmp = elem[x];
        elem[x]=elem[y];
        elem[y]=tmp;
    }

    public int poll(){
        int tmp = elem[0];
        swap(0,usesize-1);
        usesize--;
        shifDown(0,usesize);
        return tmp;
    }
    public boolean isFull(){
        return usesize==elem.length;        //当有效位和数组的长度相同时，代表数组满了
    }

    public void offer(int val){
        if(isFull()){                   //判断数组是否满了，如果满了就进行扩容
            this.elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usesize]=val;              //将新插入的数据置为数组最后
        usesize++;                      //有效位加1
        shifUp(usesize-1);          //进行向上调整，传入插入数据的下标，视为孩子节点

    }
    public void shifUp(int child){
        int parent = (child-1)/2;       //根据孩子节点确定父亲节点
        while (child>0){                //孩子节点还大于头节点的时候，就继续遍历
            if(elem[child]>elem[parent]){   //孩子节点的值大于父亲节点的值，就进行交换
                swap(child,parent);
                child=parent;           //将父亲节点给孩子，进行向上调整
                parent=(child-1)/2;     //父亲节点给自己的父亲节点
            }else {
                break;
            }
        }
    }

    public void getElem(){
        for (int i = 0; i < elem.length; i++) {
            System.out.println(elem[i]);
        }
    }


}

测试代码

public class Main  {
    public static void main(String[] args) {
        MyBigQueue myBigQueue = new MyBigQueue();
       int[] arr = {27,15,19,18,28,34,65,49,25,37};
       myBigQueue.initElem(arr);
       myBigQueue.CreatBigQ();
        System.out.println("=========");
        myBigQueue.poll();
        System.out.println("=========");
        myBigQueue.offer(99);
        myBigQueue.offer(78);
        myBigQueue.offer(108);
        System.out.println("=========");
        myBigQueue.getElem();




    }
}