案例输入一组数据需要用最快的方法拿到这个堆数据中的最大或者最小的K个数字数据结构思路使用大根堆小根堆来计算如果需要获得最大K个数字就使用小根堆为什么要用到小根堆呢------------------分割线----------------我们来思考一下假设我们使用大根堆当堆的数量k已经满了这时候来了一个数字n这个n比根顶的数字要大那么我们是不是要插入插入方法是什么呢如果将头部根顶的替换了那肯定不行最大的值都替换了肯定不满足最大值了如果将最后一个值替换了我们从不知道最后一个值是不是最小的也会替换错啊。来我们举个例子这是一个标准的大根堆此时来了一个57我们知道肯定要把最小的14替换掉那怎么替换呢根本不知道堆里哪个最小。所以我们如果换一种思维使用小根堆呢堆算法思路按照堆的定义即可编码1、即所有根节点的值都要比子节点的值要大。2、当堆创的容量还没有满时新来的值直接赋值到数组尾部然后进行从底部到顶部上浮操作。2、当堆创的容量已经满了时若新来的值比顶部还要小以小根堆为例直接舍弃不需要这个值。3、当堆创的容量已经满了时若新来的值比顶部要大将该值覆盖顶部值即heap[0]newVale;再从顶部到尾部下沉操作代码示例publicclassTopK{privateint[]heap;privateintsize;// 当前元素个数privateintcapacity;// 最大容量publicTopK(intcapacity){this.capacitycapacity;heapnewint[capacity];size0;}//插入元素从底部往上浮动publicvoidadd(intval){if(size0){heap[size]val;size;return;}if(sizecapacity){if(valheap[0]){//如果新来的元素比顶部的元素要大那么顶部最小元素直接覆盖成新来的元素从顶部向下沉heap[0]val;swiftDown();}else{//如果新来的元素比顶部的还要小直接丢弃}}else{swiftUp(val);}}//删除堆顶元素将最后一个元素赋值给第一个元素然后从顶部下沉size需要-1publicvoidpop(){heap[0]heap[size-1];heap[size-1]Integer.MAX_VALUE;swiftDown();}publicvoidswiftDown(){for(inti0;i(size-2)/2;i){if(i*22size){if(heap[i]heap[i*21]){swap(i,i*21);}continue;//终止此次循环}if(heap[i]heap[i*21]||heap[i]heap[i*22]){//比它的左右子树都要大swap拿到最大的值if(heap[i*21]heap[i*22]){swap(i,i*22);}else{swap(i,i*21);}}}size--;}publicvoidswiftUp(intval){heap[size]val;//开始向上浮for(intisize;i0;i--){intparentIndex(i-1)/2;//拿到父节点的nodeif(heap[i]heap[parentIndex]){//新来的元素比父节点还要小swap(i,parentIndex);}}size;}privatevoidswap(inti,intj){inttempheap[i];heap[i]heap[j];heap[j]temp;}publicstaticvoidmain(String[]args){TopKhnewTopK(6);h.add(11);h.add(932);h.add(82);h.add(754);h.add(62);h.add(543);h.add(4);h.add(321);h.add(224);h.add(1);h.add(10);h.pop();h.pop();h.pop();h.pop();h.pop();}}