本文共 6192 字，大约阅读时间需要 20 分钟。
又这么几种问题：、。
前者是一个固定的范围，而后者是一个变化的范围（当然了，你也可以看作若干个固定范围的快照）。解决以上问题的一个思路是排序，则难以避免需要扫描整个数组的值，而基于堆排序的时间复杂度是O（n*logK）调整的时间复杂度取决于堆的高度，将K个元素组成一个堆（数组形式的完全二叉树），因此可以调整的时间复杂度就是logK，如果你对整个数组建堆那么调整的时间复杂度就是logN
基于堆去做topK，是一个排除法的思路。
以求当前数组最小值为例，我先拿前K个元素建立一个大顶堆，那么堆顶元素必然是当前最大元素，那么当我遇到第K+1个元素，如果K+1比堆顶元素还大则直接忽略，如果第K+1个元素小于堆顶元素，我就把堆顶元素poll()移除，然后再做一个调整，最终堆顶将又是一个最大元素（比刚才移除的小）…最终遍历完整个数组，我们没做一次调整，就是就是将一个局部最大值移除的过程，有些更大的值甚至不进入offer()。相当于对一个数组移除了n-k个局部最大值，那么剩余的便是K个最小值，而最终堆首便是第K小的值。
总结：堆中构造TopK最大的本质是排除数组中Top(n-k)最小，因此我们需要一个能够快速拿到当前堆最小值的调用，并且排除这个最小的值后调整。
一句话：求Top大用小顶堆，求Top小用大顶堆。public int[] getLeastNumbers(int[] arr, int k) { PriorityQueue pq = new PriorityQueue<>((a, b) -> b - a); for(int i:arr){ if(pq.size() i){ //排除一个局部最大值，加入一个新元素并调整 pq.poll(); pq.offer(i); } } } int[] res = new int[k]; int index=0; while(k-->0){ res[index++]=pq.poll(); } return res; } java的priorityQueue底层就是一个堆（默认是小顶堆，可以通过构造函数传入比较器对象调整为大顶堆），其中offer()和poll()都涉及堆调整操作。
补充：大数据下的TopK
如果数据多到无法直接载入内存，可以将数据对应的大文件拆分成若干个小文件（至少这些文件对应的数据能够一次载入内存），然后依次读入这些文件，并且在内存中只维护一个大小为K的堆/优先队列，最终这些数据全部被扫描，而且堆/优先队列中保存就是K个数字，堆顶就是对应的Topk
堆排序的过程也是一个排除的过程——假如我们想要对大小为N的数组进行排序，那么我们便可以先对这个数组建立一个大小为N的堆，这个堆其实是一个数组，但是堆建立完毕不代表数组已经有序了，堆建立完毕只是表示：当前堆的堆顶一定是一个最值。
而排序的过程就是把这个最值往目标数组移动，然后调整堆的过程。假如我排序升序，我们我可以使用一个大顶堆，每次把堆顶拿走，然后放入到当前数组的末尾，并且对前N-1个堆进行调整。最终使得整个数组都是升序排列的。（注意，因为是对数组整体建堆，因此每次拿到的堆顶一定是全局最大的、全局第二大、全局第三大…而前面TopK仅对K个元素建堆）堆排序时一般都是升序——大顶堆，堆顶元素会和末尾元素（这里的末尾是依次收缩的）交换，因此原地交换使得空间复杂度为O（1），你也可以使用一个第三方数组、然后小顶堆，每次拿到最小的往第三方数组中放，但是这样空间复杂度就上升到O（n）了。这里主要指小顶堆也能实现对应效果，但是一般使用大顶堆
堆排序涉及两个操作：堆化、调整。其中堆化就是将N个元素依次放入堆中，然后进行一次自上而下的调整。而构建有序数组的过程实际上是复用了原数组，要把arr看作一个堆数组和一个逻辑上的结果数组。堆数组中拿出一个最值放入结果数组，因此结果数组的构成伴随着堆数组的缩小
public static void heapSort(int[] arr){ for (int i = arr.length/2-1; i>=0; i--) { adjustHeap(arr,i,arr.length); } for(int j =arr.length-1;j>0;j--){ //顶堆元素放入尾部，然后进行一次堆调整 int temp =arr[j]; arr[j] =arr[0]; arr[0]=temp; adjustHeap(arr,0,j); } } 上面的arr.length-1是一种优化，前N-1个结果数组的值就位，那么最后一个值相当于直接从堆数组迁移到逻辑上的结果数组。
总结：堆排序要看作两个组成部分——【1】建立大小为N的堆【2】将堆元素迁移到结果数组（一般结果数组会复用堆数组达到原地交换，一部分人可能这里一开始看不明白）
public static void adjustHeap(int arr[],int i,int length){ int temp =arr[i]; for ( int k =i * 2 + 1 ;k < length; k =k * 2 + 1) { if(k+1 上面的代码是自上而下调整堆，从在[i…length]之间的堆节点进行调整，其中k代表i的孩子节点，循环的过程中i和k不断变化，其中循环内涉及i和k的逻辑交换，真正的赋值是循环外的arr[i]=temp。
相当于一开始i位置对应的值为temp，循环的过程中i与孩子k进行了交换，因此之后比较使用的值仍然是temp，因为后续的比较实际上是i和k交换导致i称为k的孩子，i与k的地位互换，因此后续的“爷孙比较”其实还是“父子比较”
priorityQueue继承了collection接口、queue接口，功能很杂，但是最具有特色的功能还是offer、poll。
队列默认大小是11，这个长度只是初始数组大小，优先队列是无界的，即使超过maxArraysize也会继续扩容。底层是一个object数组。优先队列还可以接受sortedSet 、collection类型。两个参数的构造函数可以传入比较器。
private void heapify(){ for(int i=size/2-1;i>=0;i--) siftDownComparable(i,(E)queue[i]);} 如果传入的是collection类型，则判断对象是否是sortedSet和priorityQueue类型，然后调用initFromCollection方法和heapify方法进行堆化
public boolean offer(E e) { if (e == null) throw new NullPointerException(); //元素不可以为null modCount++; int i = size; if (i >= queue.length) //底层数组满时才扩容 grow(i + 1); minCap=i+1 size = i + 1; if (i == 0) //空，直接放入 queue[0] = e; else //将元素放入数组尾部，然后进行向上调整 siftUp(i, e); return true;} 优先队列重写了父类的add方法，本质上就是调用offer，不抛出异常
优先队列默认小顶堆，因为优先队列每次poll都是取出queue[0]，然后调整，因此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出的元素看似是有序的，但是优先队列内部并不是有序的，因此使用迭代器迭代数组元素则并不是有序的，它只保证poll()的返回值是有序的（当前极值）。如果想输出有序队列，应该使用poll()去探测队列元素。
参考jdk源码，我们可以做一个简单的实现。
【1】仅支持peek、offer和poll 【2】不支持比较器和比较类型（jdk源码中首先将传入的对象转换为comparable类型或者使用comparator.compare（a,b）进行比较），仅使用int 【3】底层使用Integer数组 【4】不支持扩容，指定元素数量或者传入源数组 【5】不做严格的校验如空、满等int size; Integer[] arr;
提供最基础的字段，一个用于保存元素，一个用于保存当前堆节点数量（元素个数）
public MyPQ(int size){ arr = new Integer[size]; } public MyPQ(Integer[] nums){ arr=nums; size=nums.length; heapify(); } 提供两个构造器：【1】传入堆容量，初始化一个数组，后面可以手动添加元素【2】传入一个数组，相当于省去了手动添加元素的步骤
private void heapify(){ for(int i =size/2-1;i>=0;i--){ adjustDown(i,arr[i]); } } 其中堆化其实就是扫描每个元素，进行一次自下而上的调整（堆排序的第一步就是这个）。
public void offer(Integer x){ int targetIndex =size; if(targetIndex==arr.length){ System.out.println("满"); }else { if(targetIndex==0){ arr[0]=x; }else { adjustUp(targetIndex,x);//把x放入尾部，然后向上调整 } size++; } } 插入元素时，如果堆中是空的，那么就没必要进行调整操作了。如果存在元素，那么将元素尾部后进行一次自下而上的调整。
private void adjustUp(int index,Integer value){ while(index>0){ int parent = (index-1)/2; if(arr[parent]<=value)break; arr[index]=arr[parent]; index=parent; } arr[index]=value; } 其实自下而上调整和自上而下的调整道理差不多。adjustUp，循环中每次拿到的是父节点去做判断，看看是否需要调整，直到到达根或者break。
最终只要两个结果，判断到某一个父节点，不满足条件break。或者一直判断到根退出循环，最终根结点被更新为value（其实还是不断地逻辑交换罢了）public Integer poll(){ if(size==0){ System.out.println("空");return null; } size--; int cur = size; Integer res = arr[0]; Integer last = arr[cur]; arr[cur]=null; if(cur!=0){ adjustDown(0,last);//把尾元素插入首部，然后进行一次向下调整 } return res; } 移除堆顶结点，然后将尾结点放入堆顶结点后进行一次自顶向下的调整。（如果堆中只有一个元素那么不进行调整）
private void adjustDown(int index,Integer value){ int len = size; for(int child=index*2+1;child =value)break; arr[index]=arr[child]; index=child; } arr[index]=value; } 和堆排序的adjust一模一样，只不过此时不指定尾部，尾部总是堆数组末尾。循环中不断拿到孩子节点，进行逻辑交换。而index初始对应的值就是value，最终的结果要么是没有进行任何交换，或者某个孩子的值被更新为value（以及中途的一些交换）
public Integer peek(){ return (size==0)?null:arr[0]; } peek操作就是拿到首节点，没什么特别的。
转载地址：http://cttzi.baihongyu.com/