【Java容器源码】PriorityQueue 源码分析

妖狐艹你老母 2022-12-11 06:25 253阅读 0赞

先来看看 PriorityQueue 继承关系，核心成员变量及主要构造函数：

// 可以看到 PriorityQueue 只是一个普通队列，并不是一个阻塞队列
    public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
        
    	
    	// 通过数组保存队列数据，队列节点是Object
    	// 这里采用的其实是堆这种数据结构，后面元素的排序也是采用的堆排序
    	// 小顶堆，每次 poll、peek 都能得到最小的元素
    	transient Object[] queue;
    	
    	transient int modCount = 0; 
    	private int size = 0
    	
    	// 比较器，priortyqueue是优先队列，所以比较器是必须的
    	private final Comparator<? super E> comparator;
    	
    	// 数组默认初始容量
    	private static final int DEFAULT_INITIAL_CAPACITY = 11;
    	// 数组最大容量
    	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    	
    	//----------------------------------构造函数------------------------------
    	// 构造函数一：空参构造
    	public PriorityQueue() {
        
    		// 默认初始容量，无比较器
            this(DEFAULT_INITIAL_CAPACITY, 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;
        }
    }

## 1.结构分析 ##

**堆是什么？**

堆在逻辑上一棵完全二叉树，所以可以通过数组进行数据存储，而其余的树大多采用链式结构进行数据存储

*  堆分类：
    
     *  大顶堆：大顶堆就是无论在任何一棵（子）树中，父节点都是最大的
     *  小顶堆：小顶堆就是无论在任何一棵（子）树中，父节点都是最小的。PriortyQueue 采用的就是小顶堆
 *  堆的两种操作：
    
     *  上浮：一般用于向堆中添加新元素后的堆平衡
     *  下沉：一般用于取出堆顶并将堆尾换至堆顶后的堆平衡
 *  堆排序：利用大顶堆和小顶堆的特性，不断取出堆顶，取出的元素就是堆中元素的最值，然后再使堆平衡

> PS：这里只做简介，想了解堆的代码实现及更多操作的同学可以参考 [【数据结构】Java实现堆：堆的各种操作&堆排序][Java]。

**Comparable 对比 Comparator？**

这里再说一下 Comparable 接口和 Comparator 接口，它俩的作用都是提供了同一类型下不同对象实体比较的方式，所以这里主要关注它们的区别：

1）Comparable 接口

*  一般用作**内部比较器**，需要实体对象实现Comparable接口并重写 compareTo 方法
 *  比较时调用**实体对象的** compareTo 方法

public interface Comparable<T> {
        
        public int compareTo(T o);
    }

2）Comparator 接口

*  一般用作**外部比较器**，提前写好实现类并重写compare方法后，然后作为参数传入需要比较器的方法。
 *  比较时直接向**比较器中**传入两个需要比较的对象。下面是一个示例：

// Comparator作为参数，匿名类，省略实现
    // Dog：要比较的类型
    Collections.sort(list, new Comparator<Dog>() {
        
            // 重写compare方法，参数是两个待比较的对象
            public int compare(Dog o1, Dog o2) {
        
            	// 比较策略
            	return o2.age - o1.age;
            }
    });

> 注意：因为 Comparator 是接口所以不能 new，但可作为匿名类相当于省略了实现类。

## 2.入队 ##

### add() ###

public boolean add(E e) {
        
        	// 调用offer
            return offer(e);
    }

### offer() ###

offer 方法首先会判断是否需要扩容，然后再根据队列是否为决定空放入元素

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; // size++
        	
            if (i == 0)
            	// 如果队列为空直接将元素放到队首
                queue[0] = e;
            else
                // 上浮
                // 可以这么理解，队列（数组）中所有元素已经是排好序的，而新元素会追加到数组末尾，所以为了保证总体有序，可能需要将新元素上浮（前移）
                siftUp(i, e);
            return true;
    }

> 注：因为 PriortyQueue 也是需要通过比较后得到元素放入的具体位置，所以不允许添加 null（跟 TreeMap 类似）。

### siftUp() ###

判断比较时是用自定义比较器 Comparator，还是用对象实体的 compareTo 方法

private void siftUp(int k, E x) {
        
            if (comparator != null)
            	// 有自定义比较器，就用自定义比较器，调用 siftUpUsingComparator
                siftUpUsingComparator(k, x);
            else
            	// 无自定义比较器，就用元素的Comparable方法，调用 siftUpComparable
                siftUpComparable(k, x);
    }

### siftUpComparable() ###

通过实体对象的 compareTo 方法进行比较，完成新元素的上浮，使队列（数组）总体顺序是：小 => 大。具体过程请看注释：

// k：当前队列实际大小的位置（没有新元素），x：要插入的元素
    private void siftUpComparable(int k, E x) {
        
        	// 将x强转为Comparable，可以调用CompareTo比较
            Comparable<? super E> key = (Comparable<? super E>) x;
        	    
        	// 通过不断与父节点进行比较，最后找到正确的位置
            while (k > 0) {
        
                // 得到k的父节点索引，即对 k 进行减倍
                int parent = (k - 1) >>> 1; 
                // 得到父节点的数据
                Object e = queue[parent]; 
                
                // 如果 x 比 parent 大，表示当前位置就是正确的位置
                if (key.compareTo((E) e) >= 0) 
                    break;
                    
                // x 比 parent 小，则将parent交换到x的位置
                queue[k] = e;  
                // 继续上浮，直到找到一个比 x 小的 parent
                k = parent; 
            }
            // 已将找到了合适的位置，将 x 放入
            queue[k] = key; 
    }

## 3.出队：poll() ##

出队其实就是将队首，也即小顶堆的堆顶返回，然后通过下沉操作使堆恢复。

public E poll() {
        
            if (size == 0)
                return null;
            int s = --size; // size--
            modCount++;
        	// 取队首
            E result = (E) queue[0];
            
            // 保存数组最后一个元素，也即堆尾
            E x = (E) queue[s];
            // 将堆尾删除
            queue[s] = null;
            if (s != 0)
            	// 下沉（将堆尾x放到堆顶位置，然后下沉）
                siftDown(0, x);
            return result;
    }

## 4.获取队首：peek() ##

public E peek() {
        
        	// 直接将arr[0]返回
            return (size == 0) ? null : (E) queue[0];
    }

## 5.扩容：grow() ##

扩容的本质就是数组拷贝，所以问题就在于新数组到底要多大：

*  oldCap < 64 —> newCap = oldCap\*2 + 2
 *  oldCap >= 64 —> newCap = oldCap \* 2
 *  newCap > Max —> newCap = Integer.MAX\_VALUE

private void grow(int minCapacity) {
        
            int oldCapacity = queue.length;
            // newCap
            int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                             (oldCapacity + 2) :
                                             (oldCapacity >> 1));
            // 防止溢出，即超出最大容量
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
        	// 将拷贝后的大数组再赋给queue
            queue = Arrays.copyOf(queue, newCapacity);
    }

[Java]: https://blog.csdn.net/weixin_43935927/article/details/108859896