【数据结构】关于优先级队列（堆），你了解内部原理吗？（超详解！！！）

用户11288949

发布于 2024-09-24 13:45:11

770

发布于 2024-09-24 13:45:11

文章被收录于专栏：用户11288949的专栏

📚️1.优先级队列

1.1优先级队列的概念

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适。

比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位

在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

📚️2.优先级队列的模拟（重点）

2.1什么是堆

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

总结：总的来说，根结点分为左右两棵树，每棵树都满足根结点大于（小于）其子结点，叫做大根堆（小根堆）

2.2堆的存储

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，

对于完全二叉树有以下性质：

• 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2 • 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子 • 如果2 * i + 2 • 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

这里小编在前几期二叉树讲过博客地址： http://t.csdnimg.cn/bnfaS

2.3堆的创建🌟🌟

1.引言

对于堆而言，虽然是一个完全二叉树，但是在创建过程中其实并没有用到二叉树的相关知识，其内部原理是顺序表，数组的运用，并且由于要涉及根结点与子结点的大小比较所以要用到上述公式，进行解决。

2.思路分析

图解：

在每次判断后我们要进行子结点的大小比较，然后进行与根结点的大小比较，然后再进行交换（这里小编将创建大根堆），然后判断交换后的根结点是否满足大根堆条件，此时就要向下再次判断，最终实现大根堆的创建

3.代码实现

1.对的初始化实现创建

public class PriorityQueue {
    public int usedSize=9;
    public int elme[];
    public PriorityQueue(){
        this.elme=new int[usedSize];
    }

    public void creatArray(int array[]){
        for (int i = 0; i <array.length ; i++) {
            elme[i]= array[i];
        }
    }

注解：小编这里为了方便在主函数实现数据替换。

2.实现堆的创建

 public int[] creatQueue(){
        creatArray(elme);
        for (int i = (elme.length-2)/2; i >=0 ; i--) { //对每个根节点进行调整
            downQueue(elme,i);
        }
       return elme;
    }
    //此时进行向下调整
    public void downQueue(int elem[],int parent){ 
        int child=2*parent+1;                          //每个根结点的孩子结点
        while (child<usedSize){                        //循环实现交换
            if(elem[child]<elem[child+1]&&(child+1)< usedSize){
                child++;
            }
            if(elem[parent]<elem[child]){              //孩子结点的交换
                swap(parent,child,elem);
            }
            parent=child;                       //判断交换后的树的每个根结点与子结点
            child=parent*2+1;
        }
    }

//交换方法

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

注解：这里孩子节点等于父亲节点的求法，小编就不再多说了，至于这里的外部循环，就是判断当交换后，需要再次进行二次判断，并且交换，每次交换后，父亲结点等于孩子结点的位置下标，然后再次求其孩子结点，实现向下判断，（那么此时的外部循环就是实现向下循环的条件）

2.4堆的插入 🌟🌟

1.思路

首先当堆满的时候要进行扩容，其次当我们插入时，一般在尾部进行插入，然后进行向上调整，又因为，向上调整是向下调整过后的堆，那么就只用看一条树，就是插入尾部的那条树。此时就不需要进行位置是否正确的再次判断。

2.代码实现

public int[] offer(int key){
        if (isFull()){
            this.elme=Arrays.copyOf(elme,elme.length*2);
        }
        elme[usedSize]=key;
        int child=usedSize;
        int parent=(usedSize-1)/2;
        while (true){
            if(elme[parent]<elme[child]){
                swap(parent,child,elme);
            }else {
                break;
            }
            child=parent;
            parent=(parent-1)/2;
        }
        return elme;
    }



 private boolean isFull(){       //判断堆是否满了
        return usedSize== elme.length;
    }

注解：这里小编在尾部插入元素后就进行父子结点与插入结点的判断并交换，然后每次交换，父亲与孩子的节点索引就要进行变化，若当父亲结点大于孩子结点，就直接跳出循环。

2.5堆的删除🌟🌟

1.思路

这里小编认为删除堆顶元素，就将堆顶元素与末尾元素进行交换，然后有效数据减一，那么就不会对末尾元素进行操作，然后对前面的元素进行向下调整。

2.代码实现

 public int[] poll(){

        swap(0,usedSize-1,elme);
        usedSize--;
        downQueue(elme,0);
        return elme;
    }

📚️3.常用接口的介绍

3.1PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

• PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象 • 不能插入null对象，否则会抛出NullPointerException • 没有容量限制（取决于JVM内存管理，分配机制），可以插入任意多个元素，其内部可以自动扩容 • PriorityQueue底层使用了堆数据结构 • PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

3.2PriorityQueue常用接口介绍

PriorityQueue的构造方式：

代码如下：

// 创建一个空的优先级队列，默认容量11
PriorityQueue<Integer> q1 = new PriorityQueue<>();

// 创建一个空的优先级队列，底层的容量为initialCapacity
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);


ArrayList<Integer> list = new ArrayList<>();
list.add(4);
list.add(3);
list.add(2);
list.add(1);
// 用ArrayList对象来构造一个优先级队列的对象
// q3中已经包含了4个元素
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());

PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

代码实例：

public class prioritytest {
    public static void main(String[] args) {
        PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
        p.offer(4);
        p.offer(3);
        p.offer(2);
        p.offer(1);
        p.offer(5);
        System.out.println(p.peek());
    }
}
class IntCmp implements Comparator<Integer> { 
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

输出为5，那么就是完成了大堆的创建。

内部原码如下：

这里的if语句是实现比较的关键，当我们重写compare方法时，如果O2-O1<0那么就说明要进入位置交换实现大根堆，相反那么O1-O2>0那么就不交换，就实现小根堆。

3.3其他函数功能介绍

这里还有clear(),与isEmpty()代表清空与判断是否为空

代码实例：

 int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};
    // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
// 否则在插入时需要不多的扩容
// 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
    PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
for(int e:arr){
        q.offer(e);
        }
        System.out.println(q.size()); // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素
// 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
        q.poll();
        q.poll();
        System.out.println(q.size()); // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素
        q.offer(0);
        System.out.println(q.peek()); // 获取优先级最高的元素
// 将优先级队列中的有效元素删除掉，检测其是否为空
        q.clear();
        if(q.isEmpty()){
        System.out.println("优先级队列已经为空!!!")
        }
        else{
        system.out.println("不空")
        }

🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！

💪💪💪以上就是本期内容了，感兴趣的话，就关注小编吧。

😊😊 期待你的关注~~~ ————————————————

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

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

队列