PriorityQueue是什么? 看过后才知道原来这么简单!

    上篇文章里我们了解到ArrayDeque是Queue的实现,而PriorityQueue是Queue的一种变体实现.在刷算法题
的时候经常能用到,今天来讲讲PriorityQueue.

概述

我们都知道Queue是一个先进先出的队列,而PriorityQueue则是在队列的基础上增加了优先级的特性,是一个基于小顶堆的无解队列.
举个栗子:

    在游乐园门口有很多人在排队进场,这就是一个`Queue`.这时暴发户小明想插队提前进场,`Queue`显然就不符合了,
因为`Queue`是严格按照`FIFO`原则取数据的.我们需要用优先队列`PriorityQueue`,`PriorityQueue`区别于`Queue`,
它取元素的顺序跟元素的优先级有关,每次取的都是队列中优先级最高的元素.

源码分析

结构图

继承关系

    public class PriorityQueue<E> extends AbstractQueue<E>
        implements java.io.Serializable {

AbstractQueue是Queue和AbstractCollection的共同子类,提供了对Queue的基本实现.PriorityQueue继承自AbstractQueue必须实现offer(E)``peek()``poll()等函数.

类中属性

/** 版本号 */
private static final long serialVersionUID = -7720805057305804111L;

/** 默认初始容量 */
private static final int DEFAULT_INITIAL_CAPACITY = 11;

/** 核心数组 */
transient Object[] queue;

/** 元素数量 */
private int size = 0;

/** 比较器,如果当前使用元素自然排序,此变量为null */
private final Comparator<? super E> comparator;

/** 记录 涉及到结构变化的次数(offer/remove/clear等) */
transient int modCount = 0;

/** 数组的最大容量 尝试分配更大的数组可能会导致OutOfMemoryError:请求的数组大小超过VM限制  */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

    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(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

前几个构造器都比较简单,我们重点看后面带初始元素的.PriorityQueue在带初始元素的构造函数上做了一个分类的优化.

    public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        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类型时,是直接通过initElementsFromCollection函数把元素复制到queue里,因为SortedSet本身就是排序过的.

    private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        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本身也是排好序的可以直接使用,但这里做了一层检测,防止开发者自己的实现不是排序或不是堆的情况从而导致复制出现问题.

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

其余的都通过initFromCollection处理.initFromCollection函数分为两个步骤.

    private void initFromCollection(Collection<? extends E> c) {
        // 初始化元素,复制数组
        initElementsFromCollection(c);
        // 调整数组,建堆
        heapify();
    }
    
    private void heapify() {
        // 从最后一个非叶节点开始向下调整
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            // 调整位置
            siftDown(i, (E) queue[i]);
    }

核心函数

堆操作函数

siftUp和siftDown这两个函数可以说是PriorityQueue中最重要的了.PriorityQueue中元素的添加删除都是通过堆操作来实现的.

// 向上调整堆
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
    
// 向下调整堆
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

siftUp和siftDown函数里都有两个调整函数,一个是使用Comparator的调整一个是不使用的,两者区别不大.这里主要讲解不使用的比较器的调整.

siftUp 向上调整

    /**
     * k 元素的位置
     * x k位置上的元素
     */
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        // 向上调整的条件
        while (k > 0) {
            // 获取父节点 (node - 1) / 2
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            // 和其父节点比较
            // 当 x 大于其父节点时就不用调整了
            if (key.compareTo((E) e) >= 0)
                break;
            // x 小于其父节点, 则和父节点位置互换
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

siftUpComparable向上调整比较简单主要是通过和父节点的比较互换来完成.

siftDown 向下调整

    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        // 向下调整,调整的都是非叶节点
        // (size-1)/2 是最后一个非叶节点
        while (k < half) {
            // 左子节点
            int child = (k << 1) + 1;
            Object c = queue[child];
            // 右子节点
            int right = child + 1;
            // 找出左 右子节点里最小的
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
                
            // 和 最小子节点比较
            // 比最小子节点大时,满足条件,无需继续了
            if (comparator.compare(x, (E) c) <= 0)
                break;
            
            // 比最小子节点小时,和子节点互换,继续调整
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

siftDownUsingComparator向下调整则是通过和子节点的比较互换来完成.

添加函数

    /** 添加元素  为null 抛异常 */
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        // 检测扩容
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        // 队列为空时,无需调整
        if (i == 0)
            queue[0] = e;
        else
            // 向上调整元素位置
            siftUp(i, e);
        return true;
    }
    
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // 容量小则翻倍, 否则增长50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        
        // 对最大容量进行检测处理
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            
        // copy
        queue = Arrays.copyOf(queue, newCapacity);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

通过offer(E)函数即可知道PriorityQueue是不允许插入Null值的,同时每次都是在容量满的时候进行扩容.根据当前容量的大小来进行动态扩容100%或50%,通过siftUp来进行添加元素同时调整元素位置.如下图:

获取函数

    public E peek() {
        // 获取堆顶元素
        return (size == 0) ? null : (E) queue[0];
    }

删除函数

    // 删除堆顶元素
    public E poll();
    
    // 删除指定元素
    public boolean remove(Object o);

E poll()

    // 删除堆顶元素
    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;
    }

poll()函数即取出并删除堆顶元素,再提尾元素到堆顶向下调整.如下图:

boolean remove(Object o)

    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

remove(o)函数删除指定元素,先根据indexOf函数获取元素的下标.

    private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

indexOf函数为直接遍历数组查找元素,再调用removeAt函数删除元素.

 private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }
    
    private E removeAt(int i) {
        modCount++;
        int s = --size;
        if (s == i) // 删除最后一个元素
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            // 向下调整
            siftDown(i, moved);
            if (queue[i] == moved) {
                // queue[i] == moved 说明当前满足堆结构
                // 需要向上调整
                siftUp(i, moved);
                if (queue[i] != moved)
                    // 返回moved 用于迭代器,本文不介绍.
                    return moved;
            }
        }
        return null;
    }

removeAt函数相比于poll函数多了个向上调整的步骤,这是为了防止向下调整后满足queue[i] == moved条件,即位置不动便满足堆结构,这时候就需要向上调整了来调整moved的准确位置.
如下图,删除元素10:

经过siftDown后,其满足queue[i] = moved.此时i位置和子节点满足堆结构,但i位置和其父节点不满足,此时需要通过siftUp来再次调整位置.

此时才算是调整结束.

结语

Java中PriorityQueue是一个基于数组结构来实现的优先队列.它虽然实现了Queue接口,但区别于一般的队列,元素存取通过小顶堆实现以优先级排序,底层默认以自然顺序排列,支持自定义比较器,每次取出的元素都是权值最小的,同时注意PriorityQueue不允许插入null值.

注: PriorityQueue非线程安全,如若多线程操作请使用PriorityBlockingQueue.

最后

以上就是耍酷外套为你收集整理的PriorityQueue是什么? 看过后才知道原来这么简单!的全部内容，希望文章能够帮你解决PriorityQueue是什么? 看过后才知道原来这么简单!所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。