java堆排序解決topk問題,Java 實作 堆排序 快速排序 以及 TopK問題(一)

問題是 從大小為N的無序數組裡面取K個最大值

最早想到的辦法是冒泡K輪，但是後來思考到，堆排序和快速排序，可以更好的實作取K個最大值。

堆排序Java實作

public class Main {

public static void main(String[] args) {

int[] arr={5,62,81,63,13,43,34,5,8,9,6,44};

int k=5;

heapBuild(arr,arr.length); //建樹

for(int x=0;x

System.out.print(arr[0]+" ");

swap(arr,0,arr.length-1-x); //交換第一個值和最後一個值(将根和最後一個葉子交換)

Fix(arr,0,arr.length-1-x);//遞歸修正

}

}

private static void heapBuild(int[] arr,int len) {

for(int i=len/2-1;i>=0;i--){//從後周遊所有度大于一的節點

Fix(arr,i,len); //修正該子樹

}

}

private static void Fix(int[] arr, int i,int len) { //

int left=i*2;

int right=i*2+1;

int max=i;

if (left < len && arr[left] > arr[i]) {

max = left;

}

if (right < len && arr[right] > arr[max]) {

max = right;

}

if(i!=max){

swap(arr,max,i);

Fix(arr,max,len);

}

}

private static void swap(int[] arr, int a, int b) { //交換指派

int temp=arr[a];

arr[a]=arr[b];

arr[b]=temp;

}

}

輸出為 81 63 62 44 43

堆排序實作取topK,複雜度為O(klogn)