堆排序求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;

}