数据结构：7.PriorityQueue

AI5小时前发布 beixibaobao
2 0 0

【目标】

        1.掌握优先级队列的意义所在

        2.掌握优先级队列的常用基本操作

        3.熟悉PriorityQueue的底层逻辑、学会使用PriorityQueue

1.优先级队列

1.1 概念

        队列是一种先进先出(FIFO)的数据结构。但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列（所谓优先级， 就是把一组数据的某个特性作为指标、然后把这组数据按照与这个指标的指重新进行排序，最靠近这个指标的数据优先级就越高）

        其实优先级队列和队列没有太大的逻辑关系，他并不是和普通队列一样：

        比如【3，1，4，2】，普通队列出是【3，1，4，2】，但是如果指定最大的数据优先级最高，那么我出就是【4，3，2，1】，这和普通队列的大部分特性并不相同。

        他之所以叫做优先级队列，因为它实现了 Queue 接口，拥有 offer()、poll()、peek() 等队列行为，所以叫“队列”。其实他的底层是堆（完全二叉树+堆规则）

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

1.2 优先级队列的模拟实现

        JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

1.2.1 堆的概念

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

        也就是说堆的本质上是个数组，但是他是根据某些特定规则、结合完全二叉树形态来建立的数组。

        1.大根堆

        对于每一个节点，都比它的左节点和右节点大。

数据结构：7.PriorityQueue

        2.小根堆

        对于每一个节点，都比它的左节点和右节点小。

数据结构：7.PriorityQueue

        堆的性质：

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

1.2.2 堆的存储方式

        堆是一棵完全二叉树，因此如果对堆进行层序遍历，那么按照这个顺序把每个数据存入数组中，就是堆的存储方式。

数据结构：7.PriorityQueue

        对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原完全二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

        将元素存储到数组中后，可以根据二叉树的性质进行还原。假设i为节点在数组中的下标，则有：

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

1.2.3 堆的创建

1.堆数组的创建（JAVA内置的PriorityQueue堆的调整就是向下调整，因此我们日常中说的建堆就是向下调整的过程）

        首先在这里明确一件事：堆在逻辑结构上是完全二叉树没错，但是其底层实现是数组。也就是说对堆创建是根据完全二叉树的形态、然后把数组等效做完全二叉树然后对其进行操作。

public calss TestHeap {
   public int[] elem;//表示堆数组
    public int usedSize;//表示这个数组的存储数据的个数
    public TestHeap() {
        //在创建堆对象的时候、默认这个对象的初始容量为10
        this.elem = new int[10];
    }
    public void creatElem(int[] elem) {
        //用来处理一个需要处理的数组
        for (int i = 0; i < elem.length; i++) {
            this.elem[i] = elem[i];
            this.usedSize++;
        }
    }
}
2 堆的调整（建堆）

对于堆{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其进行调整呢？（本章示范都是调整成大根堆）

数据结构：7.PriorityQueue

2.1向下调整（JAVA内置的PriorityQueue堆的调整就是向下调整，因此我们日常中说的建堆就是向下调整的过程）

        这个"向下"指的是操作对象（指针/下标）在数组中的移动方向，并不是指遍历的方向。

数据结构：7.PriorityQueue

        这里有一个问题：如上图这样做，真的就处理完了吗？接着往下看。

数据结构：7.PriorityQueue

        调整后的堆如下：

数据结构：7.PriorityQueue

    public void creatHeap() {
        //创建大根堆
        for (int p = ((this.usedSize - 1) - 1) / 2; p >= 0 ; p--) {
            //每一次循环表示每一个需要处理的节点
            siftDown(p,this.usedSize);
        }
    }
    public void siftDown(int p, int size) {
        int c = p * 2 + 1;
        while(c < size) {
            //一旦c的位置超出了，那么就说明 已经创建完毕
            if (c + 1 < size && this.elem[c] < this.elem[c + 1]) {
                //确保c位置是最大的数
                c++;
            }
            if(this.elem[p] < this.elem[c]) {
                swap(p, c);
                p = c;
                c = c * 2 + 1;//一直是左子树
            }else{
                //表示比最大的都大，那么就不用进行处理
                break;
            }
        }
    }

        问：向下调整（建堆）的时间复杂度是多少呢？

数据结构：7.PriorityQueue

        答：向下调整（建堆）的时间复杂度为O(n)。

2.2 向上调整

        同样的，这个"向上"指的是也是操作对象（指针/下标）在数组中的移动方向，并不是指遍历的方向。

        向上调整应用于插入数据，我们在插入数据处讲向上调整。

1.2.4 堆的常用操作

1.数据的插入

数据结构：7.PriorityQueue

        调整后的堆如下：

数据结构：7.PriorityQueue

    public void offer(int data) {
        if(elem.length == this.usedSize) {
            this.elem = Arrays.copyOf(this.elem,this.elem.length * 2);
        }
        this.elem[this.usedSize] = data;
        siftUp(this.usedSize);
        this.usedSize++;
    }
    public void siftUp(int size) {
        int c = size;
        int p = (c - 1) / 2;
        while(p >= 0) {
            if(this.elem[p] < this.elem[c]) {
                swap(p, c);
                c = p;
                p = (p - 1) / 2;
            }else {
                //表示插入合格
                break;
            }
        }
    }

        这里的siftUp就是向上调整。

        问：向上调整的时间复杂度是多少呢？

数据结构：7.PriorityQueue

        答：向上调整的时间复杂度为O(n*Logn)。

2.数据的删除

        首先删除肯定是要删除优先级最高的，也就是出队列的是队头。

数据结构：7.PriorityQueue

    public void pop() {
        //删除的时候肯定是删除优先级高的
        swap(0,this.usedSize - 1);
        this.usedSize--;
        siftDown(0,this.usedSize - 1);
    }
    public void siftDown(int p, int size) {
        int c = p * 2 + 1;
        while(c < size) {
            //一旦c的位置超出了，那么就说明 已经创建完毕
            if (c + 1 < size && this.elem[c] < this.elem[c + 1]) {
                //确保c位置是最大的数
                c++;
            }
            if(this.elem[p] < this.elem[c]) {
                swap(p, c);
                p = c;
                c = c * 2 + 1;//一直是左子树
            }else{
                //表示比最大的都大，那么就不用进行处理
                break;
            }
        }
    }

        由于插入和删除的最坏情况都是从最后一个到第一个节点、且每一层都只需要遍历一个节点。也就是说，无论插入或者删除，他们的最坏情况下，最大次数语句执行次数都是h，而

2^h – 1 = n -> h = log2(n + 1)，所以说时间复杂度为O(logn)。

3.优先级最高数据的打印
    public int peek() {
        //打印优先级最高的
        return elem[0];
    }

2.PriorityQueue

2.1PriorityQueue的特性

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

数据结构：7.PriorityQueue

关于PriorityQueue的使用要注意：

1. 使用时必须导入PriorityQueue所在的包，即： import java.util.PriorityQueue;

2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常

3. 不能插入null对象，否则会抛出NullPointerException

4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容

5. 插入和删除元素的时间复杂度为O(logn)

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

2.2 PriorityQueue常用方法

2.2.1 构造方法

        常用的构造方法有以下三种、其余的仅作了解。

构造器 一句话用途 关键记忆点
PriorityQueue() 创建一个默认容量（11） 的空堆 最常用，无参构造
PriorityQueue(int initialCapacity) 创建一个指定容量的空堆 容量必须 >= 1
PriorityQueue(Collection<? extends E> c) 用一个已有的集合来建堆 普通集合会触发 O(n) 的建堆过程

数据结构：7.PriorityQueue

数据结构：7.PriorityQueue

数据结构：7.PriorityQueue

2.2.2 插入/删除/获取优先级最高的元素

方法 功能 返回值 特殊说明（重点） 时间复杂度
offer(E e) 插入元素 true（成功） 1. 元素不能为 null（否则抛 NullPointerException）
2. 空间不够时会自动扩容 		O(log n)（向上调整）
poll() 删除并返回堆顶（优先级最高的元素） 堆顶元素，或 null（如果队列为空） 移除堆顶后，内部会进行向下调整 O(log n)（向下调整）
peek() 查看堆顶（不删除） 堆顶元素，或 null（如果队列为空） 只查看，不删除 O(1)
size() 获取有效元素个数 元素个数 – O(1)
isEmpty() 检测队列是否为空 true（空），false（非空） – O(1)
clear() 清空队列 void（无返回值） 移除所有元素，重置内部状态 O(n)

3.应用

3.1 堆排序

        堆排序是根据大根堆、小根堆的性质——优先级最高的在0号位置。其中比较的核心是：相反做法。也就是说：要升序——建立大根堆，要降序——建立小根堆

        比如对一个数组进行排序，要求升序。那么我们只需要把这个数组创建成大根堆，0号位置肯定是最大的，然后依次交换0号位置的数据和最后一个位置的数据。

    public void heapSort() {
        //从小到大排序
        int end = this.usedSize - 1;
        //需要建立大根堆、这里直接进行示范->能够保证最大的一直在最上面，然后依次放到最后面
        while(end > 0) {
            swap(0, end);
            siftDown(0,end);
            end--;
        }
    }

3.2 Top-K问题

        Top-K问题：求最大，或者最小的前k个数据。解决的方法有很多：比如对给定的数组进行多次调整，这里我们提供一种新的方法。

数据结构：7.PriorityQueue

    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0) return ret;
        //前k个最小的数
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Intcmp());
        for (int i = 0; i < k; i++) {
            //把前k个给存入优先级队列中
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if(arr[i] < priorityQueue.peek()) {
                //那么出
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        //都走完了，说明最小的都是在优先级队列中，然后依次按照顺序出就可以
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

4.比较

4.1 与比较相关的知识点

4.1.1 equals

  • equals() 是 java.lang.Object 类里的方法
  • 返回值类型：boolean类型
  • 调用的格式：对象1.queals(对象2)
public class Students {
    public int age;
    public String name;
    public Students(int age, String name) {
        this.age = age;
        this.name = name;
    }
    @Override
    public boolean equals(Object o) {
        if (o == null || getClass() != o.getClass()) return false;
        Students students = (Students) o;
        return age == students.age && Objects.equals(name, students.name);
    }
}
public class Test {
    public static void main(String[] args) {
        Students students1 = new Students(13,"zhangSan");
        Students students2 = new Students(18,"liSi");
        //重写前：
        /*boolean ret = students1.equals(students2);
        System.out.println(ret);//false->默认情况下比较的是引用本身*/
        //重写后：
        boolean ret = students1.equals(students2);
        System.out.println(ret);//false->会根据重写的具体要求来进行判断
    }
}

        总结：equals() 的返回值是 boolean类型，他的不足之处在于一个对象只能按照一个指标来进行比较

4.1.2 compareTo

  • compareTo() 是 java.lang.Comparable 接口里的方法
  • 返回值类型：int类型
  • 调用的格式：对象1.compareTo(对象2)
  • 注意:Comparable<T>中的T 和 compareTo(T o)中的T 要一致。并且无论是按照哪个指标进行比较，这个T都必须是比较的对象的类型，比如：T必须是Students类型，然后在compareTo方法中再讨论按照什么指标进行比较
public class Students implements Comparable<Students> {
    public int age;
    public String name;
    public Students(int age, String name) {
        this.age = age;
        this.name = name;
    }
    /*@Override
    public int compareTo(Students o) {
        return this.age - o.age;
    }*/
    @Override
    public int compareTo(Students s) {
        //引用类型不能直接相减
        return this.name.compareTo(s.name);
        //这个compareTo 是 String类 里面的
    }
}
public class Test {
    public static void main(String[] args) {
        Students students1 = new Students(13,"zhangSan");
        Students students2 = new Students(18,"liSi");
        //compareTo（实现接口Comparable）：返回值为int类型
        int ret = students1.compareTo(students2);
        System.out.println(ret);//14->会根据重写的具体要求来进行判断
    }
}

        总结：compare() 的返回值是 int类型，他的存在弥补了compareTo()只能进行一个指标比较的不足。

        小提醒：Comparator接口中只有compare()方法需要重写，Comparable接口中只有compareTo()方法需要重写

4.1.3 compare

  • compare() 是 java.lang.Comparator 接口里的方法
  • 返回值类型：int类型
  • 调用的格式：比较器对象.compareTo(对象1，对象2)
  • 注意:Comparator<T>中的T 和 compare(T o1, T o2)中的T 要一致。并且无论是按照哪个指标进行比较，这个T都必须是比较的对象的类型，比如：T必须是Students类型，然后在compare方法中再讨论按照什么指标进行比较 

        总结：compareTo() 的返回值是 int类型，他的不足之处在于一个对象只能按照一个指标来进行比较

        也就是说equals()和compareTo()的不足之处一样。只不过equals()返回值类型是 boolean类型，而compareTo()返回值类型是 int类型

4.1.4 总结equals()、compareTo()、compare()方法

对比维度 equals compareTo compare
所属类/接口 Object 类 Comparable 接口 Comparator 接口
所在的包 java.lang java.lang java.util
是否需要手动导包 ❌ 不需要（java.lang 自动导入） ❌ 不需要（java.lang 自动导入） ✅ 需要（import java.util.Comparator）
方法签名 public boolean equals(Object obj) public int compareTo(T o) public int compare(T o1, T o2)
参数个数 1 个（传入对象） 1 个（被比较对象） 2 个（两个比较对象）
返回值类型 boolean（true / false） int（负数 / 0 / 正数） int（负数 / 0 / 正数）
谁调用这个方法？ 对象自己调用：s1.equals(s2) 对象自己调用：s1.compareTo(s2) 比较器对象调用：comp.compare(s1, s2)
核心作用 判断两个对象内容是否相等 定义对象的自然顺序（默认排序规则） 定义自定义顺序（灵活、可插拔的排序规则）
是否需要修改原类？ ✅ 需要重写 equals 方法 ✅ 需要实现 Comparable 接口 ❌ 不需要修改原类
是否能定义多种比较规则？ ❌ 不能（只能定义一种相等逻辑） ❌ 不能（只能有一种自然顺序） ✅ 能（可以定义无数种不同的比较器）
null 值是否安全？ ❌ 不安全（s1.equals(null) 会报 NullPointerException） ❌ 不安全（需要自己手动处理 null） ⚠️ 可以通过 Comparator.nullsFirst() / nullsLast() 安全处理
Java 8+ 推荐写法 重写 equals + Objects.hash() 实现 Comparable 接口 Comparator.comparing(类::字段)（Lambda）
设计目的 用于相等性判断（内容是否相同） 用于单一固定排序（类自带默认顺序） 用于灵活多变的排序（策略模式）

4.2 PriorityQueue的比较

        PriorityQueue的比较场景：

        当堆中的每个节点都是引用类型时，肯定不能根据引用本身来进行优先级判断，否则会报异常，如下：

数据结构：7.PriorityQueue

        而我们解决这种问题的方法：就是指定一个比较的指标，让对象按照这个指标进行优先级排序，这时候有两种方法：

4.2.1 结合PriorityQueue()的定义，传参比较器对象（常用）

数据结构：7.PriorityQueue

class ByAge implements Comparator<Students> {
    @Override
    public int compare(Students s1, Students s2) {
        return s1.age - s2.age;
    }
}
public class Students {
    public int age;
    public String name;
    public Students(int age, String name) {
        this.age = age;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Students{" +
                "age=" + age +
                ", name='" + name + ''' +
                '}';
    }
    public static void main(String[] args) {
        Students s1 = new Students(18,"zhangSan");
        Students s2 = new Students(33,"liSi");
        PriorityQueue<Students> priorityQueue = new PriorityQueue<>(new ByAge());
        priorityQueue.offer(s1);
        priorityQueue.offer(s2);
        System.out.println(priorityQueue.peek());//Students{age=18, name='zhangSan'}
    }
}

4.2.2 结合PriorityQueue()的定义，在自身指定比较指标（不常用）

        在进行优先级排序的时候，如果comparator == null，也就是说没有比较其对象的时候，那么就会调用siftUpComparable(int k, T x, Object[] es)方法

数据结构：7.PriorityQueue

        也就是说，这时候只需要对对象类本身重写compareTo()方法，指定比较指标，那么就可以进行优先级排列了。

public class Students implements Comparable<Students>{
    public int age;
    public String name;
    public Students(int age, String name) {
        this.age = age;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Students{" +
                "age=" + age +
                ", name='" + name + ''' +
                '}';
    }
    @Override
    public int compareTo(Students s) {
        return this.age - s.age;
    }
    public static void main(String[] args) {
        Students s1 = new Students(18,"zhangSan");
        Students s2 = new Students(33,"liSi");
        PriorityQueue<Students> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(s1);
        priorityQueue.offer(s2);
        System.out.println(priorityQueue.peek());//Students{age=18, name='zhangSan'}
    }
}
© 版权声明
文章版权归作者所有，未经允许请勿转载。

相关文章

标签云