PriorityQueue的详解

 2.2插入/删除/获取优先级最高的元素

（1）offer底层代码展示 

private static final long serialVersionUID = -7720805057305804111L;
 
private static final int DEFAULT_INITIAL_CAPACITY = 11;
 
 transient Object[] queue;
 
private int size = 0;
 
private final Comparatorsuper E> comparator;

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;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

siftUp：

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

siftUpUsingComparator：

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

siftUpComparable：

 private void siftUpComparable(int k, E x) {
        Comparablesuper E> key = (Comparablesuper E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

 （2）PriorityQueue的扩容方式：

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));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

如果容量小于 64 时，是按照 oldCapacity 的 2 倍方式扩容的

如果容量大于等于 64 ，是按照 oldCapacity 的 1.5 倍方式扩容的

如果容量超过 MAX_ARRAY_SIZE ，按照 MAX_ARRAY_SIZE 来进行扩容

 代码：

class Solution {
       public int[] smallestK(int[] arr, int k) {
            int[] ret = new int[k];
        if (arr==null||k<=0){
            return ret;
        }
        imp imp = new imp();
        PriorityQueue priorityQueue = new PriorityQueue<>(imp);
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
 
        for (int i = k; i < arr.length; i++) {
            int top=priorityQueue.peek();
            if(top>arr[i]){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;
    }
}
 
class imp implements Comparator {
    public int compare(Integer o1,Integer o2) {
        return o2-o1;
    }
}

解析：

对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都 不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决，基本思路如下：

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 

以上为我个人的小分享，如有问题，欢迎讨论！！！ 

都看到这了，不如关注一下，给个免费的赞