数据结构优先级队列PriorityQueue

本章讲述数据结构中的优先级队列的学习，感谢大家的支持！欢迎大家踊跃评论，感谢大佬们的支持！我的博客主页

优先级队列的概念

优先级队列与传统的队列：队列（Queue)的结构是采取先进先出后进后出的原则，每次出队的都是首元素，而每次插入元素只能将元素插入队尾。

而优先级队列(PriorityQueue)指的是具有优先级别的队列(特殊队列)，根据指定类型的大小，每次出队的元素都是该类型中最大或者是最小的值，具有优先级。

二叉堆逻辑结构：上述讲到类型中最大或者最小的元素小根堆与大概堆它们的结构也是不同的，小跟堆是以由小到大的上下顺序来连接，（无需左右大小比较）。 而大根堆是由大到小的顺序上下来连接（无需左右大小比较）。

优先级队列的本质上是以数组的形式来存储，然后通过层序遍历的方式来创建了一个二叉堆的数据结构。 以下⬇️是优先级队列的图片。

如何实现优先级队列？

因为是通过数组存储的，它们的储存顺序都是固定的从0下标开始到x，求得该节点的左子树为2x+1，右子树为2x+2（左子树的+1）
如果想要由孩子节点求得其父亲节点的坐标，通过（x-1）/2。

PriorityQueue优先队列实现

由最后一个父亲节点开始比较，通过size-1的下标得到数组长度(size-1)/2获取到最后父亲节点的位置，然后通过父亲节点的左2parent+1/右树(2parent+2)来进行比较，得到最大值在与父亲节点比较，如果大于就进行交换。
每次交换完后，让其child继续向下移动查看孩子节点是否大于根节点。

大根堆实现

  //大根堆
    public void siftDown(int parent,int usedSize){
        int child=(2*parent)+1;
       while(child<usedSize) {
           //child最大范围就是usedSize的长度，这里的usedSize为10
           if (child+1<usedSize&&elem[child] < elem[child + 1]) {
               //取得最大值进行比较
               child = child + 1;
           }
           if (elem[child] > elem[parent]) {
               swap(child,parent);
               //parent往下找左右子树如果范围不满足要求，不在进行查找
               parent=child;
               child=(2*parent)+1;
           } else {
               //因为只需要拿到最大值与根节点交换，如果不笔比parent大说明左右树都小，直接跳出循环
               break;
           }
       }
    }
    public void swap(int c,int p){
        int tmp=elem[c];
        elem[c]=elem[p];
        elem[p]=tmp;
    }

小根堆实现

步骤相同只需要更换为小于即可

 //小根堆
    public void siftDown(int parent,int usedSize){
        int child=(2*parent)+1;
       while(child<usedSize) {
           //child最大范围就是usedSize的长度，这里的usedSize为10
           if (child+1<usedSize&&elem[child] > elem[child + 1]) {
               //取得最大值进行比较
               child = child + 1;
           }
           if (elem[child] < elem[parent]) {
               swap(child,parent);
               //parent往下找左右子树如果范围不满足要求，不在进行查找
               parent=child;
               child=(2*parent)+1;
           } else {
               //因为只需要拿到最大值与根节点交换，如果不笔比parent大说明左右树都小，直接跳出循环
               break;
           }
       }
    }
    public void swap(int c,int p){
        int tmp=elem[c];
        elem[c]=elem[p];
        elem[p]=tmp;
    }

插入元素

当已经通过向下筛选创建好堆之后，我们可以通过向上筛选来调整每个数组的位置，从而将我们插入的元素通过大小比对放在对应位置上，其他元素也通过向上筛选的方式由大到小进行了更换

 public void swap(int c,int p){
        int tmp=elem[c];
        elem[c]=elem[p];
        elem[p]=tmp;
    }
    //插入一个元素到栈堆中
    public void push(int val){
        if(isEmpty())throw new RuntimeException("The array element is empty.");
        if(isFull())elem= Arrays.copyOf(elem,2*elem.length);
        elem[usedSize]=val;//将val值给到最后一个位置
        shiftUp(usedSize);
        usedSize++;
    }
    public void siftUp(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;
            }
        }
    }

删除元素

删除元素我们可以将对首的元素将队尾的元素进行互换，并将队尾元素的下标值删除，后续进行覆盖，然后通过向下筛选，设定根节点为0下标互换的位置，进行向下筛选。

  public int poll(){
        if(isEmpty())return -1;
        int firstVal=elem[0];
        swap(0,usedSize-1);//0下标与最后一个下标进行更换
        usedSize--;//删除最后一个下标的元素，后续进行覆盖
        siftDown(0,usedSize);
        return firstVal;
    }

堆排序

将堆中的元素由小到大进行排序。我们使用大根堆来进行排序，将0下标值与最后下标值进行交换，end为最后下标值，然后向下筛选重新获取最大的节点值，每次的有效元素数量-1（由最后一个下标开始–直到为0，获取由小到大的元素）。

 public void heapSort(){
        int end=usedSize-1;//最后一个小表
        while(end!=0) {
            swap(0, end);
            siftDown(0,end);
            end--;
        }
    }

PriorityQueue包注意事项

1.PriorityQueue放置的元素必须能够进行大小比较，不能插入无法比较的大小的对象，否则会抛出ClassCastExcetion异常。
2.不能插入null对象，否则会抛出NullPorinterException空指针异常。
3。没有容量的限制，可以插入多个元素内部会自动扩容。
4.插入和删除元素的时间复杂度为O(log2N)
5.PriorityQueue地层使用了堆数据结构。
6.PriorityQueue默认情况下是小跟堆存储。
7.使用时必须倒入PriorityQueue所在的包。

感谢大家观看