PriorityQueue

Java 面试 PriorityQueue 集合
Java
发布日期:   2024-04-28
更新日期:   2024-05-11
文章字数:   2.6k
阅读时长:   10 分
阅读次数:  

PriorityQueue

PriorityQueue，优先队列，同样也遵循FIFO的原则，但是会根据优先级来处理对象

普通队列和PriorityQueue的区别：

  • 元素出队：
    • 普通队列会按照先进的元素先出队，后进的元素后出队的规则维护队列
    • 优先队列会按照元素的优先级来决定出队的顺序，默认情况下优先级越小的优先出队
  • 逻辑存储结构：
    • PriorityQueue底层实际上是使用小顶堆形式的二叉堆，值最小的元素优先出队

二叉堆的性质

  1. 二叉堆是一棵完全二叉树，在节点个数无法构成满二叉树（每层都放满节点）时，叶子节点会出现在最后一层，且不满足双数情况下的叶子节点会尽可能地靠左。

  2. 小顶堆的情况下，父节点的值永远比其两个子节点要小，大顶堆反之

  3. 二叉堆的大小关系永远只针对父子孙这样的层级，拿小顶堆来举例，我们不能说第二层的节点就一定比第三层节点小

    image-20240508163816996

PriorityQueue适合解决找最大值或最小值的问题

基于MinHeap实现一个简单的PriorityQueue

实现一个简单的小顶堆（MinHeap） | Feliks

实现简单的优先队列（PriorityQueue） | Feliks

JDK自带的PriorityQueue分析

从以下四方面来查看源码：

  1. 构造器
  2. 入队操作
  3. 出队操作
  4. 查看优先级最高的元素

构造器

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

public PriorityQueue(PriorityQueue<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}

优先队列的构造器中，有一个需要用户同时传入initialCapacity和comparator的构造器

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

前者用于初始化一个数组queue

image-20240511143848666

后者是一个比较器，这说明queue数组的元素在进行入队操作时是需要比较的，这个queue数组就是优先队列底层用到的二叉小顶堆

此外，优先队列还支持将不同的集合对象类转为PriorityQueue

public PriorityQueue(Collection<? extends E> c) {
    // SortedSet本身有序，所以直接获取其比较器，按其规则将元素转移到PriorityQueue中
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    // 如果集合的类型是PriorityQueue则直接获取比较器，将传入的元素移到我们的OPriorityQueue中
    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);
    }
}

public PriorityQueue(SortedSet<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initElementsFromCollection(c);
}

因为SortedSet本身就是有序的，所以PriorityQueue直接获取其比较器

调用的initElementsFromCollection内部

private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] es = c.toArray();
        int len = es.length;
        if (c.getClass() != ArrayList.class)
            es = Arrays.copyOf(es, len, Object[].class);
        if (len == 1 || this.comparator != null)
            for (Object e : es)
                if (e == null)
                    throw new NullPointerException();
        this.queue = ensureNonEmpty(es);
        this.size = len;
    }

该方法将传入的集合转为数组，如果传入的集合类型不是ArrayList动态数组类型就调用Arrays.copyOf方法将集合正确转为一个Object类型的数组，最后检查Object数组内是否为空，不为空则将此数组赋给queue数组并记录数组长度

当我们调用构造器传入的集合类型是PriorityQueue类型时，会调用另一个方法：initFromPriorityQueue

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

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

该方法判断传入的c是不是PriorityQueue类型，是则直接获取传入的PriorityQueue中的queue数组，否则调用上述的initElementsFromCollection，然后调用heapify方法将queue数组转为小顶堆

对比一下官方的heapify方法和我们写的heapify方法看看

官方：

private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1;
    final Comparator<? super E> cmp;
    if ((cmp = comparator) == null)
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i], es, n);
    else
        for (; i >= 0; i--)
            siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}

自定义的：

private void heapify() {
    // 将最后一个非叶子节点的元素往前遍历并使用siftDown操作插入到堆中
    for (int i = parentIndex(list.size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}

官方实现的在逻辑上获取父节点操作时使用了高效的右移运算，其余与我们的实现差不多，都是将最后一个非叶子节点的元素往前遍历并使用siftDown操作插入到堆中

入队操作

offer方法

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    siftUp(i, e);
    size = i + 1;
    return true;
}
  1. 判断传入的元素e是否为空
  2. 设置新插入的位置为size
  3. 判断数组容量是否足够，不足则调用grow方法对数组进行扩容
  4. 调用siftUp方法将元素放入队列

siftUp方法

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

判断有没有自定义的比较器，有则使用自定义的比较规则

private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        // >>>：无符号右移，相当于(k - 1) / 2
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = x;
}

没有则将x转为Comparable对象进行比较

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        // >>>：无符号右移，相当于(k - 1) / 2
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

整个siftUp做的事基本如下：

  1. 获取要入队的元素当前索引的父索引
  2. 根据父索引找到元素e
  3. 根据compareTo比较如果新节点的值x比父节点的值e大，则说明当前入队操作符合小顶堆要求，直接退出循环
  4. 反之则将父节点e的值更改为入队元素x的值
  5. k指向父索引，继续循环向上比较父索引，直到找到比x还小的父节点e，退出循环
  6. 将x存到符合要求的索引位置k

出队操作

底层实际上是使用小顶堆形式的二叉堆，值最小的元素优先出队

poll方法

public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}
  1. size减一并赋值给n
  2. n如果不为0，需要维护最小堆的特性，从堆顶开始进行siftDown操作

查看优先级最高的元素

peek方法

public E peek() {
    return (E) queue[0];
}

PriorityQueue为什么要用二叉堆实现？用二叉堆实现的优势在哪？

因为带有完全二叉树性质的二叉堆，其入队和出队操作的时间复杂度都是O(nlogn)，而使用数组来实现的话，未排序的情况下入队操作的时间复杂度是O(1)，出队操作的时间复杂度是O(n)，而如果是有序数组的情况下入队是O(n)，出队是O(n)，使用二叉堆折中的情况更为合适

PriorityQueue线程安全吗？

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    siftUp(i, e);
    size = i + 1;
    return true;
}

入队操作的源码中并没有针对线程安全的处理操作，所以PriorityQueue是线程不安全的

PriorityQueue底层用什么实现的？初始化容量是多少？

PriorityQueue底层使用数组来表示优先队列， 而这个数组实际上用到了小顶堆的思想来维持元素的优先级

transient Object[] queue；

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

// siftDown操作
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x, queue, size, comparator);
    else
        siftDownComparable(k, x, queue, size);
}

默认初始化容量（DEFAULT_INITIAL_CAPACITY）为11

private static final int DEFAULT_INITIAL_CAPACITY = 11;
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

PriorityQueue使用小顶堆来实现的，那如果要让元素按从大到小的顺序排序怎么办？

正因为PriorityQueue底层的数组实现的是一个小顶堆，所以只需要在使用构造器创建PriorityQueue的时候让比较器取反即可

package Queue;

import java.util.Comparator;
import java.util.PriorityQueue;

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 this.name;
        }

        public int getAge() {
            return this.age;
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Person> personPriorityQueue = new PriorityQueue<>(Comparator.comparing(Person::getAge).reversed());

        personPriorityQueue.add(new Person("Alice", 21));
        personPriorityQueue.add(new Person("Feliks", 22));
        personPriorityQueue.add(new Person("Alex", 19));

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

    }
}

按照年龄从大到小排序，结果如下

image-20240511221954168

为什么PriorityQueue底层使用数组构成小顶堆而不是链表？

考虑空间占用的因素，用链表来存储的话需要用额外的内存空间来维护父子及左右子节点等关系，而如果使用数组，因为其地址空间是连续的，所以可以使用简单的数学公式表示父子节点的关系

为什么要维护父子节点的关系？

PriorityQueue支持传入一个集合生成优先队列，如果传入的是一个无序的List，那么在数组转二叉堆的时候需要经过heapify操作，从最后一个非叶子节点开始知道根节点为止，不断进行siftDown操作维持自身以及子孙节点之间的优先级关系

综上，使用数组可以以O(1)的时间复杂度定位到最后一个非叶子节点，通过索引减1操作可以到达下一个非叶子节点，比链表方便维护很多

文章作者: Feliks
文章链接: https://qetuop91.github.io/2024/04/28/ji-he-priorityqueue/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Feliks !
Java 面试 PriorityQueue 集合
赏
评论
  目录