top k算法的经典实现是大顶堆和小顶堆，而在JAVA中可以用PriorityQueue实现小顶堆，话不多说，直接上代码
public static List<Integer> getTopMapNum(int[] arr, int k) {
Queue<Integer> priorityQueue = new PriorityQueue();
List<Integer> topKList = new ArrayList<>();
if (arr == null || k > arr.length || k <= 0) {
return topKList;
}
for (int i : arr) {
if (priorityQueue.size() < k) {
priorityQueue.add(i);
} else {
if (priorityQueue.peek() < i) {
priorityQueue.poll();
priorityQueue.add(i);
}
}
}
while (k-- > 0) {
topKList.add(priorityQueue.poll());
}
return topKList;
}
作为程序员，只知道简单的如何实现是不够的，最好能够深入源码，下面我们就来聊一聊PriorityQueue
PriorityQueue是优先队列，作用是保证每次取出的元素都是队列中权值最小的，这里涉及到了大小关系，元素大小的评判可以通过元素自身的自然顺序（使用默认的比较器），也可以通过构造时传入的比较器。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。（下图是网上截的，只是这个讲的不是很详细，图还是可以的，所有自己再总结一下，原链接：https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7472265.html）
上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。
add()和offer
add()方法内部是调用的offer()，所以两个方法没啥区别，都是向队列中插入元素
新加入的元素可能会破坏小顶堆的性质，所以需要进行调整
/** * The number of times this priority queue has been * <i>structurally modified</i>. See AbstractList for gory details. *队列调整的次数 */ transient int modCount = 0; // non-private to simplify nested class access
/** * The number of elements in the priority queue. *队列中元素的个数 */ private int size = 0;
public boolean add(E e) {
//add方法内部调用的offer方法
return offer(e);
}
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;
}
/** * Increases the capacity of the array. *队列扩容 * @param minCapacity the desired minimum capacity */
private void grow(int minCapacity) {
//原始队列容量
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
//如果原始队列容量没有超过64，则翻倍扩容，否则扩容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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons. the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param k the position to fill
* @param x the item to insert
* 元素添加
*/
private void siftUp(int k, E x) {
//使用构造方法传进来的比较器
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);//使用默认的比较器
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super 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;
}