| Blog信息 |
|
blog名称:
日志总数:1304
评论数量:2242
留言数量:5
访问次数:7592433
建立时间:2006年5月29日 |
| |
|
 [算法]堆的应用
软件技术
lhwork 发表于 2006/12/11 11:18:17 |
| 一个文件中包含了1亿个随机整数，如何快速的找到最大(小)的100万个数
字？这类问题其实就是“优先树”算法，用堆(Heap)很容易解决。首先用含100万个数字的数组组成堆。从文件间读取数字，并插入到Heap中。如果
Heap已经满了，则删除根节点，并重整；直到所有的数字均处理完毕。
堆排序是Heap的副产品，其实它大部分时间是用在“优先决策”上，上面的例子只是其中之一，其他场所比如操作系统的任务调用、优先队列等。
public static Comparable[] findMin(int count, String fileName) {
Heap heap = new Heap(count);
try {
BufferedReader br = new BufferedReader(new FileReader(fileName));
String line;
while((line = br.readLine()) != null) {
Integer number = Integer.valueOf(line);
if(heap.isFull())
heap.delete();
heap.insert(number);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
Comparable[] ret = new Comparable[count];
int index = count - 1;
while(!heap.isEmpty()) {
ret[index--] = heap.delete();
}
return ret;
} |
|
|