前言这次介绍另一种选择排序方法，时间复杂度为O(nlogn)，称为堆排序。我将从以下几个方面来介绍：堆结构堆排序优化堆排序就地堆排序堆应用堆结构什么是堆？我给出了百度的定义，如下：堆（Heap）是计算机科学中一类特殊数据结构的总称。堆通常是一个对象数组，可以看作是一个完整的二叉树。堆总是满足以下性质：堆中节点的值总是不大于或不小于其父节点的值。堆总是一棵完全二叉树。根节点最大的堆称为最大堆，根节点最小的堆称为最小堆。下图是一个最大堆的结构：可以看出，堆中某个节点的值总是小于或等于其父节点的值。由于堆是一棵完全二叉树，所以我们可以对每一层进行编号：我们可以用一个数组来存储这些元素，那么如何确定存储位置呢？使用以下公式：父节点：parent(i)=(i-1)/2左孩子：leftChild(i)=2*i+1右孩子：rightChild(i)=2*i+2相关代码为如下：privateintparent(intindex){return(index-1)/2;}privateintleftChild(intindex){returnindex*2+1;}privateintrightChild(intindex){returnindex*2+2;}添加一个元素向堆中添加一个元素的步骤如下：大批。获取新元素的父节点在数组中的位置，比较新元素和父节点的值，如果父节点的值小于新元素的值，则两者交换。以此类推，一直向上比较，直到根节点结束。下图是添加元素的过程：添加元素的过程也叫siftUp，代码如下：//Array是一个动态数组privateArraydata;publicvoidadd(Ee){data.addLast(e);siftUp(data.getSize()-1);}privatevoidsiftUp(intk){while(k>0&&data.get(parent(k))).compareTo(data.get(k))<0){data.swap(k,parent(k));k=parent(k);}}删除一个元素删除一个元素实际上就是删除堆顶元素。步骤如下：将数组的最后一个元素与数组的第一个元素（堆顶元素）交换。交换后，删除数组的最后一个元素。让堆顶元素与左右子节点进行比较。如果堆顶元素大于左右子节点中的最大元素，则满足堆的性质，直接退出。否则，如果堆顶元素小于左右子节点中的最大元素，则将堆顶元素与最大元素进行交换，然后继续重复上述操作，但就是此时最好称堆顶元素为父节点。下图是删除元素的过程：删除元素的过程也叫siftDown，代码如下：//这里不命名为remove，而是命名为extractMax，提取最上面最大的元素theheappublicEextractMax(){Eret=findMax();//让最后一个叶子结点补到根结点，然后让它下沉//（为什么取最后一个叶子结点，因为即使最后一个叶子结点是带走，它仍然可以保持完整的二叉树)data.swap(0,data.getSize()-1);data.removeLast();siftDown(0);returnret;}privatevoidsiftDown(intk){while(leftChild(k)0){j=rightChild(k);//data[j]是leftChild和rightChild的最大值}//如果父节点大于左右孩子的最大值，那么没有问题，直接退出if(data.get(k).compareTo(data.get(j))>=0){break;}//否则交换data.swap(k,j);k=j;}}Th最大堆堆排序的完整代码通过上面的介绍，我们应该了解了堆的结构，堆的添加和删除元素的操作是如何完成的。所以对于堆排序来说，是小菜一碟，因为堆排序使用的是堆的增删操作。步骤如下：将数组中的元素逐个添加到堆（最大堆）中。添加完成后，一次取出一个元素，倒序放入数组中。堆排序代码：publicstaticvoidsort(Comparable[]arr){intn=arr.length;//MaxHeap是自己实现的最大堆MaxHeapmaxHeap=newMaxHeap<>(n);for(inti=0;i=0;i--){arr[i]=maxHeap.extractMax();}}堆排序??完成代码优化堆排序在上面的堆排序中，当我们将数组中的元素添加到堆中时，我们是一个一个的添加。有优化的方法吗？答案是肯定的，我们可以直接把数组转成堆。该操作称为Heapify。Heapify从最后一个节点开始判断父节点是否大于子节点，或者siftDown。Heapify操作的时间复杂度是O(n)，相比一个一个相加的时间复杂度是O(nlogn)，可以看出性能提升了很多。假设我们有一个数组：[15,18,12,16,22,28,16,45,30,52]，下图是对它进行Heapify的过程。优化堆排序代码：publicstaticvoidsort(Comparable[]arr){intn=arr.length;//MaxHeap是自己实现的最大堆，当传入数组作为构造参数时，就是heapifyMaxHeapmaxHeap=newMaxHeap<>(arr);for(inti=n-1;i>=0;i--){arr[i]=maxHeap.extractMax();}}//构造方法publicMaxHeap(E[]arr){data=newArray<>(arr);//堆数组的过程是从最后一个节点开始判断父节点是否大于子节点，或者siftDownfor(inti=parent(arr.length-1);i>=0;i--){siftDown(i);}}优化堆排序完整代码In-placeheapsortIn-placeheapsort可以让我们的空间复杂度O(1)，因为没有新的数组被占用.就地堆排序类似于从堆中删除元素。步骤如下：HeapifysiftDownsiftDown下图展示了原地堆排序的过程：原地堆排序代码：publicstaticvoidsort(Comparable[]arr){intn=arr.length;//heapifyfor(inti=parent(n-1);i>=0;i--){siftDown(arr,n,i);}//核心代码for(inti=n-1;i>0;i--){swap(arr,0,i);siftDown(arr,i,0);}}privatestaticvoidswap(Object[]arr,inti,intj){Objectt=arr[i];arr[i]=arr[j];arr[j]=t;}privatestaticvoidsiftDown(Comparable[]arr,intn,intk){while(leftChild(k)0){j=rightChild(k);}//如果父节点大于左右孩子的最大值，那么就没有问题，直接退出if(arr[k].compareTo(arr[j])>=0){break;}//otherwiseswapswap(arr,k,j);k=j;}}一旦我们掌握了堆，就地堆排序应用程序完整代码堆的优先级队列这个数据结构，那么优先级队列的实现就很简单了，只需要搞清楚prio是在哪些接口上rity队列需要有。JDK自带的PriorityQueue是用堆实现的优先级队列，但是需要注意的是PriorityQueue内部使用的是最小堆。PriorityQueueCompleteCodeTopK问题TopK问题就是求解topK个最大或最小的元素。元素个数不确定，数据量可能很大，甚至是源源不断的来，但是需要知道目前为止前K个最大或最小的元素。当然，问题也可能变成寻找第K大或第K小的元素。通常我们有以下解决方案：使用JDK自带的排序，比如Arrays.sort()，由于底层使用的是快速排序，所以时间复杂度为O(nlogn)。但是如果K的值很小，比如1，也就是最大值，那么就没有必要对所有元素进行排序。使用简单的选择排序，选择K次，那么时间复杂度是O(n*K)，如果K大于logn，最好快速排序！以上两种思路都是假设所有的元素都是已知的，如果元素个数不确定的话，数据还在不断的进来，就没办法了。下面提供一种新的思路：我们维护一个长度为K的数组，前K个元素为当前最大的K个元素。每一个新元素到来后，先在数组中找到最小值，将新元素与新元素合并，如果小于最小值，则什么都不做，如果大于最小值，则用新元素替换最小值.这样，数组中始终保持着最大的K个元素。不管有多少数据源，需要的内存开销是固定的，是一个长度为K的数组，但是每次来一个元素，都需要找最小值，进行K次比较。有没有办法减少比较次数？当然，这个时候堆就要出现了。我们使用最小堆来维护这K个元素。新元素只需要和根节点比较，如果小于等于根节点，则不需要改变，否则用新元素替换根节点，然后siftDown调整堆。此时时间复杂度为O(nlogK)。与上面两种方法相比，效率大大提高，空间复杂度也大大降低。TopK问题代码：publicclassTopK>{privatePriorityQueuep;privateintk;publicTopK(intk){this.k=k;this.p=newPriorityQueue<>(k);}publicvoidaddAll(Collectionc){for(Ee:c){add(e);}}publicvoidadd(Ee){//如果小于k，直接相加if(p.size()=0){//小于等于TopK中的最小值，不用改return;}//否则，用新元素替换原来的最小值p.poll();p.add(e);}/***获取当前最大的K个元素**@parama返回一个空数组，类型为*@param*@returnTopK转数组形式*/publicE[]toArray(E[]a){returnp.toArray(a);}/***获取第K大元素**@returnKth最大元素*/publicEgetKth(){returnp.peek();}publicstaticvoidmain(String[]args){TopKtop5=newTopK<>(5);top5.addAll(Arrays.asList(88,1,5,7,28,12,3,22,20,70));System.out.println("top5:"+Arrays.toString(top5.toArray(newInteger[0])));System.out.println("5th:"+top5.getKth());}}这里直接使用JDK自带的最小堆实现的优先级队列PriorityQueue。按照这个思路，可以找到前K个最小的元素，只需要在实例化PriorityQueue时传入一个反向比较器参数，然后改变add方法的逻辑即可。中值堆也可以用来求解中值，数据量可能很大，源源不断的进来。注意：如果元素个数是偶数，那么我们假设任意一个中位数都可以。有了上面的例子，这里就很容易理解了。我们使用两个堆，一个最大堆和一个最小堆，步骤如下：第一个加入的元素作为中位数m，最大堆保持元素<=m，最小堆保持>=m个元素，两个堆都不包含m。添加第二个元素e时，比较e和m，如果e<=m，则将其添加到最大堆，否则将其添加到最小堆。如果最小堆和最大堆的元素个数相差>=2，则将m添加到元素个数少的堆中，然后让元素个数多的堆去掉根节点，将其分配给m。等等等等。假设您有数组[20,30,40,50,2,4,3,5,7,8,10]。整个运行过程如下图所示：求解中位数的代码：publicclassMedian>{/***最小堆*/privatePriorityQueueminP;/***最大堆*/privatePriorityQueuemaxP;/***当前中位数*/privateEm;publicMedian(){this.minP=newPriorityQueue<>();this.maxP=newPriorityQueue<>(11,Collections.reverseOrder());}privateintcompare(Ee,Em){returne.compareTo(m);}publicvoidaddAll(Collectionc){for(Ee:c){add(e);}}publicvoidadd(Ee){//第一个元素if(m==null){m=e;return;}if(compare(e,m)<=0){//小于等于中值，加上最大堆maxP.add(e);}else{//更大比中值，加上最大堆minP.add(e);}if(minP.size()-maxP.size()>=2){//最小堆的元素个数大，即,大于中值的数//将m加入到最大堆中，然后在最小堆中取出根赋值给mmaxP.add(m);m=minP.poll();}elseif(maxP.size()-minP.size()>=2){minP.add(m);m=maxP.poll();}}publicEgetMedian(){returnm;}publicstaticvoidmain(String[]args){Medianmedian=newMedian<>();median.addAll(数组。asList(20,30,40,50,2,4,3,5,7,8,10));System.out.println(median.getMedian());}}
