软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
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 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年11日历
2017-11-18 23:48:36
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --