在1亿个随机整数中找出前1000个最大的数

直接上代码
public class Top1000 {

public static int N = 1000;

public static int LEN = 100000000;
public static int arrs[] = new int[LEN];
public static int result[] = new int[N];
public static int len = result.length;

public static int heapSize = len;

public static void main(String[] args) {
    Random random = new Random();
    for (int i = 0; i < LEN; i++) {
        arrs[i] = random.nextInt(Integer.MAX_VALUE);
    }

    //构建初始堆
    for (int i = 0; i < N; i++) {
        result[i] = arrs[i];
    }

    //构建小顶堆
    long start = System.currentTimeMillis();
    buildMinHeap();

    for (int i = 0; i < N; i++) {
        if (arrs[i] > result[0]) {
            result[0] = arrs[i];
            minHeap(0);
        }
    }
    System.out.println(LEN + "个数,求top" + N + ",耗时" + (System.currentTimeMillis() - start) + "毫秒");
    print();
}

private static void print() {
    for (int a : result) {
        System.out.print(a + ",");
    }
    System.out.println();
}


/**
 * 自底向上构建小堆
 */
private static void buildMinHeap() {
    int size = len / 2 - 1;
    for (int i = size; i >= 0; i--) {
        minHeap(i);
    }
}

/**
 * i节点为根及子树是一个小堆
 *
 * @param i
 */
private static void minHeap(int i) {
    int l = left(i);
    int r = right(i);
    int index = i;
    if (l < heapSize && result[i] < result[index]) {
        index = l;
    }
    if (r < heapSize && result[r] < result[index]) {
        index = r;
    }
    if (index != i) {
        int t = result[index];
        result[index] = result[i];
        //递归向下构建堆
        minHeap(index);
    }
}

private static int left(int i) {
    return 2 * i;
}

private static int right(int i) {
    return 2 * i + 1;
}

}

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容