堆排序求TopK(java)

建立一个长度为K的堆,求一组数据中最小的K个数

时间复杂度是O(N*logK)

package com.test;

public class topheap {

//取len个数据中最小的k个元素，维护一个顶元素最大的堆，不用对这个堆排序double heap[];

int k;//top k

int len;//共len个数据

topheap(int kk,int ll)

{

k = kk;

len = ll;

heap = new double[k+1];

}

/*

* 将data[pos]到data[end]的数据建堆

*/

public void toheap(int pos,int end,double h[])

{

int i = pos;

int j=i;

double value = h[i];

while(true)

{

if(2*i>end)

break;

double l = h[2*i];

j = 2*i;

double max = l;

if(2*i+1 <= end)

{

double r = h[2*i+1];

if(l<r)

{

max = r;

j = 2*i+1;

}

}

if(value<h[j])

{

h[i] = h[j];

i = j;

}

建立一个长度为K的堆,求一组数据中最小的K个数

else

{

break;

}

}

h[i] = value;

}

/*

* 将前k个数据建成堆

*/

public void kheap(double data[])

{

if(k>data.length)

{

System.out.println("数组元素个数不足K个");

return ;

}

//将data中的前k个元素建成堆

for(int i=0;i<k;++i)

{

heap[i+1] = data[i];

}

for(int i=k/2;i>0;--i)

{

toheap(i,k,heap);

}

}

/*

* 读入整个数组，求Top K

*/

public void getTopK(double data[])

{

//将前k个数据建堆

kheap(data);

//对K之后的数据依次读入

for(int i=k;i<data.length;++i)

{

getTopKoneByone(data[i]);

}

}

/*

建立一个长度为K的堆,求一组数据中最小的K个数

* 依次读入数据，求Top K

*/

public void getTopKoneByone(double data)

{

//只有在输入数据比堆顶元素小时才更新heap if(data<heap[1])

{

heap[1] = data;

toheap(1,k,heap);

}

}

public static void main(String args[])

{

//double[] data = {2,10,5,7,3,1,7,8};

double data[] = new double[100000];

for(int i=0;i<data.length;++i)

{

data[i] = Math.random()*100000;

}

topheap th = new topheap(10,data.length);

th.getTopK(data);

for(int i=1;i<=th.k;++i)

{

System.out.print(th.heap[i]+" ");

}

System.out.println();

/*//冒泡排序求Top K，可以比较一下

for(int i=data.length-1;i>0;--i)

for(int j=0;j<i;++j)

{

if(data[j]>data[j+1])

{

double t = data[j];

data[j] = data[j+1];

data[j+1] = t;

}

}

for(int i=0;i<th.k;++i)

System.out.println(data[i]);

*/

}

建立一个长度为K的堆,求一组数据中最小的K个数

}

本文来源：https://www.bwwdw.com/article/js9m.html