寻找TopN——在10亿数据中找到1000个最大的数

目录

问题描述

如何从10亿数据中找到前1000大的数？

解法

针对该问题，给定一个数组data，从中找出前n个最大的数。
解题思路
先维护一个具有n个数的堆，然后调整该堆为小顶堆，即每个父节点都比其子节点小。然后从剩下的数组中逐一读取数据，将读取到的数据跟堆顶比较。如果该数比堆顶小，直接丢弃；如果该数比堆顶数大，则用该数替换堆顶，重新调整该堆为小顶堆。等待所有数据处理完毕，这时候已经的小顶堆就是TopN。

public class TopN {
//	当前节点的父节点
	private int parent(int n){
		return (n-1)/2;
	}
//	当前节点的左子节点
	private int left(int n){
		return 2*n+1;
	}
//	当前节点的右子节点
	private int right(int n){
		return 2*n+2;
	}
//	构建堆
	private void buildHeap(int n, int[] data){
		for(int i=1;i<n;i++){
			int t=i;
			while(t!=0 && data[parent(t)]>data[t]){
				int temp = data[parent(t)];
				data[parent(t)]=data[t];
				data[t]=temp;
				t=parent(t);
			}
		}
	}
//	调整堆，为小顶堆
	private void adjust(int i, int n, int[] data){
		if(data[0]>=data[i]){
			return;
		}
		int temp = data[i];
	    data[i] = data[0];
	    data[0] = temp;
		int t=0;
//		调整时，堆顶比子节点大，从较小的子节点开始调整
		while((left(t)<n&&data[t]>data[left(t)])||(right(t)<n&&data[t]>data[right(t)])){
			if((right(t) < n && data[right(t)] < data[left(t)])){
				temp=data[t];
				data[t]=data[right(t)];
				data[right(t)]=temp;
				t=right(t);
			}else{
				temp=data[t];
				data[t]=data[left(t)];
				data[left(t)]=temp;
				t=left(t);
			}
		}
	}
//	寻找topN数
	public void findTopN(int n, int[] data){
		buildHeap(n,data);
		for(int i=n;i<data.length;i++){
			adjust(i,n,data);
		}
	}
//	打印
	public void print(int[] data){
		for(int i=0;i<data.length;i++){
			System.out.print(data[i]+",");
		}
	}
}

补充

这里寻找TopN的问题，也可以用分治法，类似快排。

随机选一个数t，对数组进行partition，这时数组一分为二，前一部分大于t，后一部分小于t。如果前一部分数据个数等于1000，直接结束；如果前一部分数据个数大于1000，那么在前一部分中继续partition；如果前一部分数据个数小于1000，那么在后一部分中partition。时间复杂度是o(n)，但10亿数据，占大量内存；改进：将数据写入文件中，但多次对磁盘读取，影响效率；再改进：采用分布式的思想。

在我看来，更好的是正文中介绍的方法，维护一个N个数的堆。

本文学习的是https://mp.weixin.qq.com/s/V-VhsE-5aYU3v8RA8mCgaQ