软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 研发管理 -> 利用堆排序得到前K小元素 -> 正文阅读

[研发管理]利用堆排序得到前K小元素


问题描述:在N个数中找到前K小的数(不是第K小),其中N>>K(N远大于K),并且N个数是逐渐生成的。


由于N取值很大,所以不可能把N个值全部保存下来后再通过排序的方法解决,这样做缺点有:
1、需要分配大量内存来保存这N个数
2、只需要找到前K小,其它N-K个数没必要保存
3、假如有很多组这样的N个数都需要找到前K小的数,则肯定会导致内存溢出
所以把N个值全部保存下来后再通过排序的方法解决的思路不可取。


这里借鉴堆排序(堆排序详见http://blog.csdn.net/tterminator/article/details/41055521)的方法,对每组生成的N个数找前K小只需要申请有K个存储单元的数组Arr,把N个数中的前K个数用来填充数组Arr,当Arr被填满时运行一次堆排序(这里利用的是小根堆),堆排序结束后Arr下标为0的位置存放的是这K个数中的最大值,接下来把生成的K+1到第N个数分别于Arr[0]作比较,当且仅当新生成的数字小于Arr[0]时,用这个新生成的数字替换掉Arr[0],并重新运行一次堆排序,循环反复,最终就可以找到N个数的前K小。
完整代码如下:

package test;

public class test {
	private static int max;
	private static int index;
	public static void main(String [] args){
		int [] target = new int[]{11,12,13,14,-1,-2,-3,-4,20,8};
		System.out.print("排序前:");
		for(int tmp : target){
			System.out.print(String.valueOf(tmp) + "  ");
		}
		//开始堆排序
		heap_sort(target, target.length);
		//测试搜索前10小
		int [] test = new int[]{0,1,2,3,4,5,6,7,8,9};
		for(int i = 0; i < 10; i++){
			if(test[i] < target[0]){
				target[0] = test[i];
				heap_sort(target, target.length);
			}
		}
		System.out.println();
		System.out.print("前K小值:");
		for(int tmp : target){
			System.out.print(String.valueOf(tmp) + "  ");
		}
	}

	public static void heap_sort(int [] arr, int arr_length){
		//construct heap
		for(int i = (arr_length - 1)/2; i >= 0; i--){
			sx(arr, i , arr_length - 1);
		}
		//debug
		System.out.println();
		System.out.print("建堆后:");
		for(int tmp : arr){
			System.out.print(String.valueOf(tmp) + "  ");
		}
		System.out.println();
		System.out.print("最大值:" + max + " 下标值:" + index);
		//n-1 times sx
		for(int j = arr_length - 1; j >= 0; j--){
			swap(arr, 0, j);
			sx(arr, 0, j - 1);
		}
	}
	//筛选算法
	public static void sx(int [] arr, int parent, int end){
		int flag = 0;
		int min_sub_index = -1;
		int left_sub = 2 * parent + 1;
		int right_sub = 2 * parent + 2;
		
		while(left_sub <= end && flag != 1){
			if(right_sub <= end ){
				if(arr[left_sub] < arr[right_sub]){
					min_sub_index = left_sub;
					if(arr[right_sub] > max){
						max = arr[right_sub];
						index = right_sub;
					}
				}else{
					min_sub_index = right_sub;
					if(arr[left_sub] > max){
						max = arr[left_sub];
						index = left_sub;
					}
				}
			}else{
				min_sub_index = left_sub;
				if(arr[left_sub] > max){
					max = arr[left_sub];
					index = left_sub;
				}
			}
			if(arr[parent] > arr[min_sub_index]){
				if(arr[parent] > max){
					max = arr[parent];
					index = parent;
				}
				swap(arr, parent, min_sub_index);
				parent = min_sub_index;
				left_sub = 2 * parent + 1;
				right_sub = 2 * parent + 2; 
			}else{
				flag = 1;
			}
		}
	}
	
	public static void swap(int [] arr, int src, int destinate){
		int tmp = arr[src];
		arr[src] = arr[destinate];
		arr[destinate] = tmp;
	}
}

运行结果:
排序前:11  12  13  14  -1  -2  -3  -4  20  8  
建堆后:-4  -1  -3  12  8  -2  13  14  20  11  
最大值:20 下标值:8
建堆后:-4  -3  -1  -2  11  8  13  0  12  14  
最大值:20 下标值:8
建堆后:-4  -3  -1  -2  8  0  12  1  11  13  
最大值:20 下标值:8
建堆后:-4  -3  -1  -2  1  0  11  2  8  12  
最大值:20 下标值:8
建堆后:-4  -3  -1  -2  1  0  8  3  2  11  
最大值:20 下标值:8
建堆后:-4  -3  -1  -2  1  0  3  4  2  8  
最大值:20 下标值:8
建堆后:-4  -3  -1  -2  1  0  3  5  2  4  
最大值:20 下标值:8
前K小值:5  4  3  2  1  0  -1  -2  -3  -4  

ps:在代码中加了求最大值及其下标的代码,和解决本问题没有关系,纯粹是开发时调试使用,使用时请根据个人情况删除。


......显示全文...
    点击查看全文


上一篇文章      下一篇文章      查看所有文章
2015-04-07 22:47:00  
研发管理 最新文章
拉格朗日乘数
maven之可视化项目依赖(Visualizingdepend
mac效率工具
Atitit.css规范bem项目中CSS的组织和管理
git入门
Asimplemodelfordescribingbasicsourcesofp
Linux进程管理浅析
我的openwrt学习笔记(十九):linux便捷开
2、微控制器选择
Git使用手册:为Git仓库创建Submodule
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年10日历
2018-10-24 10:42:12
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --