【Java】还在死磕算法？懂“堆”与“优先级队列”，代码效率飙升

喜欢做梦

发布于 2024-12-26 09:15:04

2750

文章被收录于专栏：学习学习

🏆堆

一、🎯什么是堆

堆的概念

堆是一种特殊的完全二叉树，如果有一个关键码的集合K={k0，k1,k2,...,kn-1},把它所有的元素按照完全二叉树的顺序存储方式在一维数组中，并满足：Ki<=K2i+1且Ki<=K2i+2（Ki>=K2i+2）i=0,1,2,3....,则称为小堆。堆有两种类型分别为大根堆和小根堆：

小根堆：根节点的值最小，父节点的值小于或等于其孩子节点的值；
大根堆：根节点的值最大，父节点的值大于或等于其孩子节点的值；

堆的性质

是一个完全二叉树；
堆的某个节点总是不大于或不小于父节点的值；

二、🀄️堆的创建

大堆

实现过程：

代码：

public class Heap {
    public int[] elem;//数组
    public int usedSize;//使用大小
    public Heap() {
        this.elem=new int[10];
    }
    //初始化
    public void initHeap(int[] elem){
        for (int i = 0; i <elem.length ; i++) {
            //初始化
            this.elem[i]=elem[i];
            //使用大小增加
            usedSize++;
        }
    }
    //建立大堆将父节点向下调整
    //思路：从从后向上将父节点向下调整；
    //父节点表示：(usedSize-1-1)/2;
    //左孩子节点表示为2*parent+1
    //1.找出左右孩子节点中的哪个元素最大
    //2.将父节点与左右孩子节点的最大值进行比较；
    //       如果小于，将元素进行交换；随后将父节点跳到孩子节点的位置，直到最后一个节点
    //       如果大于，退出该次循环，进入到下一次循环
    public void creatHeap(){
        for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
            //parent:调整的起始位置；
            //usedSize：调整的结束位置
            siftDown(parent,usedSize);
        }
    }
    public void siftDown(int parent,int usedSize){
        int child=2*parent+1;
        while(child<usedSize){
            //比较左右节点
            //如果左节点小于右节点
            //将孩子节点++，到右节点的位置
            if(child+1<usedSize && elem[child]<elem[child+1]){
                child++;
            }
            //比较父节点与子节点
            //如果小于子节点，交换两元素位置
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                //交换完，将父节点等于下一个子节点，看下一个堆是否形成大堆，
                //如果没有，继续交换
                parent=child;
                child=2*parent+1;
            }else{
                //如果大于子节点，不调整
                break;
            }                          }
    }
    private void swap(int[] elem,int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    
}
}

小堆

小堆的思路与大堆相同，只不过一个父节点比子孩子小

代码：

    private void swap(int[] elem,int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;

}
    public void creatHeap2(){
        for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
            siftDown2(parent,usedSize);
        }
    }
    public void siftDown2(int parent,int usedSize){
        int child=2*parent+1;
        while(child<usedSize){
            if(child+1<usedSize && elem[child]>elem[child+1]){
                child++;
            }
            if(elem[child]<elem[parent]){
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }                          }
    }

建堆的时间复杂度为O（n）；

测试：

    public static void main(String[] args) {
        int[] array={15,28,17,36,45,23,35,56};
        Heap heap=new Heap();
        heap.initHeap(array);
        heap.creatHeap1();
        for (int i = 0; i < heap.elem.length; i++) {
            System.out.print(heap.elem[i]+" ");
        }
        System.out.println();
        heap.creatHeap2();
        for (int i = 0; i < heap.elem.length; i++) {
            System.out.print(heap.elem[i]+" ");
        }
    }

三、🎨堆的基本操作

堆的插入

思路：

看位置是否已满，如果满了扩容；
插入元素：

将元素插入在最后一个节点后面，也就是插入在elem[uesdSize];
随后将其进行向上调整；

向上调整：将子节点进行向上调整

向上调整的实现过程：

实现代码：

    public void offer(int val){
        if(isFull()){
            this.elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        siftUp(usedSize);
        usedSize++;
    }
    private boolean isFull(){
        return this.usedSize== elem.length;
    }
    //向上调整：
    //将子节点与父节点进行比较；
         //如果大于父节点，交换；随后减子节点跳到父节点的位置，父节点跳到父节点的位置
         //小于退出本次循环
    public void siftUp(int child){
         int parent=(child-1)/2;
         //循环条件：parent>=0
         while(parent>=0){
             if(elem[parent]<elem[child]){
                 swap(elem,parent,child);
                 child=parent;
                 parent=(child-1)/2;
             }else{
                 break;
             }
         }    }}

堆的删除

堆的删除：删除堆顶元素

思路

将堆顶元素与最后一个节点元素进行交换，也就是位置0的元素与位置usedSize的元素进行交换
交换后，只有0位置开始不是大堆，所以我们从0开始进行向下调整；
调整完将使用大小减小

调整过程：

代码：

  public int poll(){
          if(isEmpty()){
              return -1;
          }
          int val=elem[0];
          swap(elem,0,usedSize-1);
          siftDown1(0,usedSize-1);
          usedSize--;
          return val;
    }
    private boolean isEmpty(){
        return this.usedSize==0;
    }

获取堆顶元素

//获取堆顶元素
    public int peek(){
        if (isEmpty()){
            return -1;
        }
        return elem[0];
    }

堆的排序（从小到大）

思路：

将最后一个元素与第一个元素进行交换，也就是将最大值放在最后一个；
随后将交换在第一个位置的元素进行向下调整到交换到最后的那些数之前；
调整完，也就是倒数第二大的元素在堆顶，将其与倒二个元素进行交换，交换完调整，其他同样如此；

调整过程：

 public void heapSort(){
        int end=usedSize-1;
        while(end>0) {
            swap(elem, 0, end);
            siftDown1(0,end);
            end--;
        }

向下调整和向上调整的区别：

区别	向下调整	向上调整
方向	父节点向下调整	子节点向上调整
比较对象	主要父节点与子节点最值进行比较	主要新插入的子节点与父节点进行比较
触发场景	删除或更新操作	插入操作

🏆优先级队列（Priority Queue）

一、📖优先级队列的概念

优先级队列：是队列的一种，遵循先进先出的原则。但是其元素有优先级之分，在出队时，优先出队，优先级最高的元素。比如在医院急诊时，优先治疗病情严重的病人。

优先级队列底层使用了堆这种数据结构。

注意事项：

使用时必须导入PriorityQueue所在的包；
PriorityQueue中放置的元素必须能够比较大小，否则抛出异常；
不能插入null对象，否则抛出异常；
没有容量限制，可以任意插入多个元素，自动扩容；

如果容量小于64进行2倍扩容；
如果容量大于等于64进行1.5倍扩容；
如果容量超过Max_ARRAY_Size,按照Max_ARRAY_Size来进行扩容；
插入和删除的时间复杂度为O（

N）；

PriorityQueue底层使用了堆数据结构；
PriorityQueue默认情况下是小堆；

如果要PriorityQueue变为大堆，可以重写compare方法：

class cmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

二、⛳️优先级队列的使用

PriorityQueue的构造方法：

PriorityQueue的方法

  public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        //插入元素
        priorityQueue.offer(24);
        priorityQueue.offer(12);
        priorityQueue.offer(35);
        priorityQueue.offer(20);
        //获取优先级最高的元素
        priorityQueue.peek();
        //删除指定元素
        priorityQueue.remove(35);
        //删除优先级最高的元素
        priorityQueue.poll();
        //.....
    }

感谢支持！！！ 🌹 🌹 🌹

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-23，如有侵权请联系 cloudcommunity@tencent.com 删除

队列