PriorityQueue 源码阅读

PriorityQueue 简介

PriorityQueue 是 Java 中的一种队列数据结构，被称为 优先级队列。它和普通队列不同，普通队列都是遵循先进先出（FIFO）的原则，即先添加的元素先出队，后添加的元素后出队。而 PriorityQueue 则是按照元素的优先级来决定出队的顺序，默认情况下，优先级越小的元素先出队。

而优先队列的逻辑存储结构和普通队列有所不同，以 PriorityQueue 为例，其底层实际上是使用 小堆顶 形式的二叉堆，即值最小的元素优先出队。

JDK 自带 PriorityQueue 使用示例

我们不妨介绍一个 PriorityQueue 的使用示例了解以下 JDK 的 PriorityQueue。

基本类型优先队列

从测试结果来看 JDK 的 PriorityQueue 中的元素也是按照升序进行优先级排序的

import java.util.PriorityQueue;
public class Main {


    public static void main(String[] args) {
        //往队列中随机添加1000_0000条数据
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        int n = 1000_0000;
        for (int i = 0; i < n; i++) {
            priorityQueue.offer(RandomUtil.randomInt(1, n));
        }

        //将优先队列中的数据按照优先级取出并存到数组中
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = priorityQueue.poll();
        }

        //如果前一个元素大于后一个元素,则说明优先队列优先级排列有问题
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) {
                throw new RuntimeException("error PriorityQueue");
            }
        }

    }
}

特殊类型优先队列

假如我们希望将自定义的对象放到优先队列中，并且我们希望优先队列按照年龄进行升序排序，那么我们就可以使用 JDK 的优先队列。

通过指明队列的泛型以及比较器，我们即可非常方便的实现一个存放自定义对象的优先队列。

public class Example {
    static class Person {
        String name;
        int age;

        Person(String name, int age) {
            this.name = name;
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public int getAge() {
            return age;
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Person> pq = new PriorityQueue<>(Comparator.comparing(Person::getAge));
        pq.add(new Person("Alice", 25));
        pq.add(new Person("Bob", 30));
        pq.add(new Person("Charlie", 20));

        while (!pq.isEmpty()) {
            Person p = pq.poll();
            System.out.println(p.getName() + " (" + p.getAge() + ")");
        }
    }
}

JDK 自带 PriorityQueue 源码分析

构造函数

先来看看这个传入数组容量 initialCapacity 和比较器的构造方法，可以看到 PriorityQueue 的构造方法要求用户传入一个 initialCapacity 用于初始化一个数组 queue，不难猜出这个数组就是优先队列底层所用到的二叉小顶堆。

同时该构造方法还要求用户传入一个 comparator 即一个2比较器，说明 queue 的元素在进行入队操作时是需要比较的，而这个 comparator 就是比较的依据。

public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        //如果初始化容量小于1则抛出异常
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

再来看看另一个核心构造方法，我们发现 PriorityQueue 支持将不同的 Collection 类转化为 PriorityQueue，对此我们不妨对每一段逻辑进行深入分析。

public PriorityQueue(Collection<? extends E> c) {
		//SortedSet类型的集合转为PriorityQueue，从SortedSet中获取一个比较器进行初始化，然后按照比较器的规则转移元素到PriorityQueue中
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        //如果集合类型是PriorityQueue则获取PriorityQueue的比较器，并将PriorityQueue的元素转移到我们的PriorityQueue中
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }

当集合类型为 SortedSet 时，因为 SortedSet 是天生有序的，所以 PriorityQueue 直接获取其比较器之后，调用了一个 initElementFromCollection 具体做了些什么。

//SortedSet类型的集合转为PriorityQueue，从SortedSet中获取一个比较器进行初始化，然后按照比较器的规则转移元素到PriorityQueue中
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }

可以看到 initElementFromCollection 只不过是将集合元素转为数组，然后赋值给优先队列底层的数组或成员变量 queue。当 a 数组未能返回一个 Object[] 类型时，则调用 Arrays.copyOf 方法将其转为一个正确的 Objectp[] 数组。

然后遍历元素进行判空，一切正常则将其赋值给 queue，并记录此时 queue 的长度。

private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        // If c.toArray incorrectly doesn't return Object[], copy it.
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null)
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }

我们再来看看 PriorityQueue 集合传入时的处理逻辑，同样的将 PriorityQueue 的比较器赋值给当前 PriorityQueue 之后，调用了一个 initFromPriorityQueue 方法，我们步入看看。

 //如果集合类型是PriorityQueue则获取PriorityQueue的比较器，并将PriorityQueue的元素转移到我们的PriorityQueue中
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }

可以看到 initFromPriorityQueue 操作就是让传入的 PriorityQueue 通过 toArray 返回底层的小顶堆数组，然后赋值给我们的 PriorityQueue，在记录一下当前 PriorityQueue 的长度。

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
           //略
        }
    }

对于一般集合，我们的逻辑会走到这里，默认设置比较器为空，然后也调用了 initFromCollection，我们步入查看逻辑。

 else {
            this.comparator = null;
            initFromCollection(c);
        }

可以看到它的实现就是调用上文所介绍的 initElementsFromCollection 将数组存到 queue 中，然后调用一个 heapify 将这个数组转为小顶堆。

 private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }

对于 JDK 实现的 heapify，可以发现获取父节点的操作使用了高效的右移运算，同样的遍历所有非叶子节点进行 siftDown 生成一个完整的小顶堆。

private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

入队操作

对于 PriorityQueue 来说，核心的入队就是 offer，它的核心步骤为:

  1. 校验元素是否为空。
  2. 设置新插入的位置为 size。
  3. 判断数组容量是否足够，如果不够则扩容。
  4. 如果是第一个元素，则直接将其放到索引 0 位置。
  5. 如果不是第一个元素，则调用 siftUp 将元素放入队列。
public boolean offer(E e) {
		//校验元素是否为空
        if (e == null)
            throw new NullPointerException();
        modCount++;
        //设置新插入的位置为size
        int i = size;
        //判断数组容量是否足够，如果不够则扩容
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        //如果是第一个元素，则直接将其放到索引0位置
        if (i == 0)
            queue[0] = e;
        else
        //如果不是第一个元素，则调用siftUp将元素放入队列
            siftUp(i, e);
        return true;
    }

在 siftUp 操作时会判断比较器是否为空，如果不为空则使用传入的比较器生成小顶堆，反之就将元素 x 转为 Comparable 对象进行比较。
因为整体比较逻辑都一样，所以我们就以 siftUpUsingComparator 查看一下进行 siftUp 操作时对于入队元素的处理逻辑。

private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

siftUpUsingComparator 是不断向上比较父节点，找到比自己大的则交换位置，直到到达根节点或者比较父节点比自己小为止，整体来说 PriorityQueue 的 siftUp 分为以下几个步骤:

  1. 获取入队元素当前索引位置的父索引 parent。
  2. 根据父索引找到元素 e。
  3. 如果新节点 x 比 e 大，则说明当前入队操作符合小顶堆要求，直接结束循环。
  4. 如果 x 比 e 小，则将父节点 e 的值改为我们入队元素 x 的值。
  5. k 指向父索引，继续循环向上比较父索引，直到找到比 x 还小的父节点 e，终止循环。
  6. 将 x 存到符合要求的索引位置 k。
private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
        //获取入队元素当前索引位置的父索引parent
            int parent = (k - 1) >>> 1;
            //根据父索引找到元素e
            Object e = queue[parent];
            // 如果新节点x比e大，则说明当前入队操作符合小顶堆要求，直接结束循环
            if (comparator.compare(x, (E) e) >= 0)
                break;
			//如果x比e小，则将父节点e的值改为我们入队元素x的值
            queue[k] = e;
            //k指向父索引，继续循环向上比较父索引，直到找到比x还小的父节点e，终止循环
            k = parent;
        }
        //将x存到符合要求的索引位置k
        queue[k] = x;
    }

出队操作

出队操作的逻辑步骤为:

  1. 判断队列是否为空。如果是，直接返回 null
  2. 如果不为空，首先将队列的 size 减 1，并将旧的末尾元素索引 s 保存下来。
  3. 将数组索引 0 位置的元素（即堆顶，也就是优先级最高的元素）暂存到 result 变量中，作为最终的返回值。
  4. 将原队列的最后一个元素 queue[s]（也就是 x）取出来。这个元素将作为新的“临时”堆顶，用于后续的堆调整。
  5. 将原队列末尾的位置设置为 null，有助于垃圾回收（GC），避免内存泄漏。
  6. 如果 s 不为 0，说明队列中不止一个元素，需要维持小顶堆的特性，需要从堆顶开始进行 siftDown 操作。
  7. 返回优先队列优先级最高的元素 result。
public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

查看优先级最高的元素

peek 方法可以不改变队列结构查看优先级最高的元素，如果队列为空则返回 null，反之返回 0 索引位置的元素。

 public E peek() {
        return (size == 0) ? null : (E) queue[0];
    }
# java # 算法 # 开发语言
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

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

更多推荐

3分钟掌握Codex技能安装：一键部署你的AI助手工具库

想要为你的Codex AI助手安装新技能？不用再手动复制文件了！skill-installer为你提供了一套完整的解决方案，让你能够从GitHub仓库快速获取和安装各种实用的Codex技能。无论你是AI开发新手还是经验丰富的开发者，这个工具都能让你在几分钟内扩展Codex的功能边界。## 为什么选择skill-installer？ 🤔在AI辅助编程的时代，Codex技能已经成为提升开发效

avatar AI编程社区

DB-GPT分布式AI数据引擎：企业级智能分析平台架构解析

DB-GPT作为新一代AI数据助手，通过分布式架构和智能代理引擎重构了传统数据分析范式。该平台将大型语言模型的自然语言理解能力与企业级数据处理需求深度融合，构建了面向生产环境的可扩展AI数据平台。其核心价值在于将复杂的SQL生成、数据分析和可视化任务转化为简单的自然语言交互，同时确保系统安全性、可追溯性和企业级可靠性。## 技术定位与生态分析在当前数据智能生态中，DB-GPT填补了传统BI

avatar AI编程社区

如何用Awesome Claude Skills将AI助手打造成你的全能创作伙伴和职业顾问

你是否曾想过，如果有一个AI伙伴能帮你完成从专业文章撰写到完美简历定制的所有工作，工作效率会提升多少倍？Awesome Claude Skills正是这样一个神奇的AI技能宝库，它汇集了1000+个精心筛选的Claude技能，覆盖内容创作、职业发展、文档处理等各个方面，让你在AI的帮助下轻松应对各种工作挑战。## 痛点分析：传统工作流程的三大瓶颈在内容创作和职业发展中，我们常常面临这样的困

avatar AI编程社区