PriorityQueue优先队列源码解析

PriorityQueue优先队列源码解析

一、什么是PriorityQueue优先队列？

PriorityQueue 一个基于优先级的*优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。该队列不允许使用 null 元素也不允许插入不可比较的对象(没有实现Comparable接口的对象)。

PriorityQueue 队列的头指排序规则最小那个元素。如果多个元素都是最小值则随机选一个。

PriorityQueue 是一个*队列，但是初始的容量(实际是一个Object[])，随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略的细节。

二、实现原理

PriorityQueue是优先级队列，它首先实现了队列接口(Queue)，与LinkedList类似，它的队列长度也没有限制，与一般队列的区别是，它有优先级的概念，每个元素都有优先级，队头的元素永远都是优先级最高的。

PriorityQueue内部是用堆实现的，内部元素不是完全有序的，不过，逐个出队会得到有序的输出。

虽然名字叫优先级队列，但也可以将PriorityQueue看做是一种比较通用的实现了堆的性质的数据结构，可以用PriorityQueue来解决适合用堆解决的问题

三、构造方法解析

add（）方法

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

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
            //数据不能为null
        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;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
         //当容量小于64按照2倍的扩容，否则1.5倍的扩容
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

//新元素(x)不断与父节点(e)比较，如果新元素(x)大于等于父节点(e)，则已满足堆的性质，退出循环，k就是新元素最终的位置；
//否则，将父节点往下移(queue[k]=e)，继续向上寻找(k=parent)
 private void siftUp(int k, E x) {
        if (comparator != null)
        //自定义实现比较器类
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

 @SuppressWarnings("unchecked")
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        //k表示size，即最后的位置
        while (k > 0) {
        //通过k找到父节点
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
            //key大于e，即新节点大于父节点
            //满足小根堆的条件 直接跳出
                break;
                //若孩子节点元素值小于父节点的值，将父节点的值与新插入元素值交换
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

    @SuppressWarnings("unchecked")
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

peek（）方法

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

remove（）方法 删除堆顶元素

 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;
    }

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

    @SuppressWarnings("unchecked")
    private void siftDownComparable(int k, E x) {
  
        Comparable<? super E> key = (Comparable<? super E>)x;
          //获取到堆大小容量一半的位置
        int half = size >>> 1;        // loop while a non-leaf
        //从根节点调整到half位置就结束
        while (k < half) {
        //找到当前节点的左孩子
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            //右孩子
            int right = child + 1;
            //找到K节点的左右孩子中最小的孩子节点
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;//上移
            k = child;//从新的节点出发继续寻找
        }
        queue[k] = key;
    }

    @SuppressWarnings("unchecked")
    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        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;
    }

四、基本特点

（1）底层使用可变数组Object[ ] queue，数组容量按需增长

（2）它是一个比较标准的队列，不是绝对标准，因为它不是严格的先进先出，内部按队列元素的大小进行了重新排序（定制排序、自然排序），所以要放入集合中的元素必须实现Comparable接口。

（3）不能存储null

（4）默认数组初始长度是11，也可以指定初始容量（也是实际会分配的容量）

（5）线程不安全。可以使用java.util.concurrent.PriorityBlockingQueue（线程安全）

（6）当遍历一个 PriorityQueue 时，没有任何顺序保证

（7）通过判断如果需要扩容，先扩容，再插入。【数组容量满了之后才会触发扩容】

（8）二叉堆【根元素最小】

（9）默认数组最大长度是MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

五、应用实例

优先队列主要应用于大数据查询之TopK的问题。

eg：获取1000000个数据，数据范围（0~1000），求出出现次数最多的10组数据

 public static void main(String[] args) {
        topMin();
    }
    public static void topMin(){
        //将100000个数据存储到ArrayList中
        ArrayList<Integer> list = new ArrayList<>(100000);
        Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            list.add(random.nextInt(1001));
        }
        //统计出现次数HashMap key：数字  value：次数
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()){
            Integer key = iterator.next();
            if (hashMap.containsKey(key)){
                hashMap.put(key,hashMap.get(key)+1);
            }
            else {
                hashMap.put(key,1);
            }
        }

        //获取出现次数最多的10组数据，优先级队列Map.Entry
        Comparator<Map.Entry<Integer, Integer>> comparator = new Comparator<Map.Entry<Integer, Integer>>() {

            //比较map中的value
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2)
            {
                //
                return o1.getValue()-o2.getValue();
            }

            @Override
            public boolean equals(Object obj) {
                return false;
            }
        };
                PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(10, comparator);
                Iterator<Map.Entry<Integer, Integer>> iterator1 = hashMap.entrySet().iterator();
                while (iterator1.hasNext()){
                    Map.Entry<Integer, Integer> entry = iterator1.next();
                    if (priorityQueue.size()<10){
                        //优先级队列中数量小于10，直接插入entry中
                priorityQueue.add(entry);
            }
            else {
                //大于10就让value与栈顶元素相比较
                Integer value = entry.getValue();
                if (priorityQueue.peek().getValue()<value){
                    priorityQueue.remove();
                    priorityQueue.add(entry);
                }
            }
            Iterator<Map.Entry<Integer, Integer>> iterator2 = priorityQueue.iterator();
            while (iterator2.hasNext()){
                Map.Entry<Integer, Integer> next = iterator2.next();
                System.out.println(next.getKey()+"出现了"+next.getValue()+"出现次数");
            }
            System.out.println();

        }

    }