java-5.查找最小的K个元素-使用最大堆
import java.util.Arrays;import java.util.Random;public class MinKElement {/** * 5.最小的K个元素 * I would like to use MaxHeap. * using QuickSort is also OK */public static void main(String[] args) {MinKElement mke=new MinKElement();int[] a={1,2,3,4,5,6,7,8};int k=4;mke.disArrange(a);System.out.println("after disarranging,the array a[]="+Arrays.toString(a));mke.findKMin(a,k);}//rearrange the array.just for test.public void disArrange(int[] a){for(int i=0,len=a.length;i<len;i++){Random random=new Random();int j=random.nextInt(len);swap(a,i,j);}}public void findKMin(int[] a,int k){int[] heap=a;//you can do this:int[] heap=new int[k].but that maybe space-cost//create MaxHeap of K elements.from the lastRootIndex to 0.int rootIndex=k/2-1;while(rootIndex>=0){reheap(heap,rootIndex,k-1);rootIndex--;}for(int i=k,len=heap.length;i<len;i++){if(heap[i]<heap[0]){heap[0]=heap[i];reheap(heap,0,k-1); }}System.out.print("the K min elements=");for(int i=0;i<k;i++){System.out.print(heap[i]+",");}}//reheap:from root to lastIndex.public void reheap(int[] heap,int rootIndex,int lastIndex){int orphan=heap[rootIndex];boolean done=false;int leftIndex=rootIndex*2+1;while(!done&&leftIndex<=lastIndex){int largerIndex=leftIndex;if(leftIndex+1<=lastIndex){int rightIndex=leftIndex+1;if(heap[rightIndex]>heap[leftIndex]){largerIndex=rightIndex;}}//Attention! should not use -->heap[root]<heap[largerIndex]<--.//I spend time to find the problem....if(orphan<heap[largerIndex]){heap[rootIndex]=heap[largerIndex];rootIndex=largerIndex;leftIndex=rootIndex*2+1;}else{done=true;}}heap[rootIndex]=orphan;}public void swap(int[] a,int i,int j){int temp=a[i];a[i]=a[j];a[j]=temp;}}