【目标】

        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.大根堆

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

        2.小根堆

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

        堆的性质：

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

1.2.2 堆的存储方式

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

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

        将元素存储到数组中后，可以根据二叉树的性质进行还原。假设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 }中的数据，如果将其进行调整呢？（本章示范都是调整成大根堆）

2.1向下调整（JAVA内置的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;
            }
        }
    }

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

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

2.2 向上调整

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

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

1.2.4 堆的常用操作

1.数据的插入

        调整后的堆如下：

    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就是向上调整。

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

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

2.数据的删除

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

    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。

关于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) 的建堆过程

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个数据。解决的方法有很多：比如对给定的数组进行多次调整，这里我们提供一种新的方法。

    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()方法

对比维度equalscompareTocompare
所属类/接口Object 类Comparable 接口Comparator 接口
所在的包java.langjava.langjava.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的比较场景：

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

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

4.2.1 结合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)方法

        也就是说，这时候只需要对对象类本身重写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'}
    }
}
# 数据结构
Logo
AI编程社区

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

码道 · 寻艺——从零构建“非遗交互式对话平台“的完整实践

avatar AI编程社区

码道：用 Python + FastAPI 快速构建一个学生信息管理接口：从零到 Swagger 在线文档

在日常开发和教学中，我们经常需要一套简单、可控、能快速上手的后端接口来演示"前后端分离"、练习 Restful API 设计，或者作为前端联调的 Mock 服务。传统做法往往是搭一套完整的 Web 工程：配置数据库、编写 DAO、引入 ORM、做请求分发……一套流程下来，光环境搭建就要花去不少时间，对于想快速验证想法、或者刚入门 API 开发的同学来说，显得过于沉重。

avatar AI编程社区

码道：从零构建学生信息管理系统 API：FastAPI 内存版 CRUD 项目全解析

FastAPI 的强大，很大程度上来自 Pydantic 的校验能力。我们写下类型声明，FastAPI 在运行时自动把它变成边界检查器。name：字符串，长度限制 1 到 50；age：整数，限制在 6 到 120 之间（ge大于等于、le小于等于）；gender：字符串，用正则限定只能是"男"“女”“其他”；email：邮箱格式字符串；grade与major：可选字段，代表班级和专业方向。

avatar AI编程社区