归并排序用来合并排好序的数组,常用于外部排序,常见的归并排序是对两个数组进行归并,如果两个数组长度为m和n的话,比较的时间最大是m+n。
新的问题是,如果有多个排好序的数组,如果进行归并? 一种可以想到的方法是:逐个进行归并排序(第一个数组和第二个数组合并,合并和的数组再和第三个数组合并...),这种情况下时间复杂度是O(n*n)。
算法导论里提到过一个用堆来进行多路排序的算法,时间复杂度是nlogn,java里面的PriorityQueue就是现成的堆的结构,实现起来还是比较方便的,代码如下:
用到的内部数据结构:
// 如果用链表存储数据,就不用这么麻烦了,
// 用数组的话,使用一个内部类保存当前值对应的数组即其在数组中的索引
// 需要实现Comparable接口,否则PriorityQueue无法对对象进行比较
private static class Element implements Comparable<Element> {
int value;
int whichArray;
int whichIndex;
Element(int value, int whichArray, int whichIndex) {
this.value = value;
this.whichArray = whichArray;
this.whichIndex = whichIndex;
}
@Override
public int compareTo(Element o) {
if (value < o.value)
return -1;
if (value > o.value)
return 1;
return 0;
}
}
主运行程序
// 程序比较丑陋是因为java不支持基本类型的泛型和动态变量名
public static void main(String[] args) {
// The arrays used for multi merge sort
Integer[] a = { 6, 19, 24, 31 };
Integer[] b = { 2, 5, 9, 67 };
Integer[] c = { 8, 20, 76, 389, 399 };
Integer[] d = { 266, 388, 736, 736, 3923 };
Integer[] e = { 38, 234, 1021, 7136, 39342 };
HashMap<Integer, Integer[]> map = new HashMap<Integer, Integer[]>();
map.put(0, a);
map.put(1, b);
map.put(2, c);
map.put(3, d);
map.put(4, e);
int arrSize = map.size();
// The PriorityQueue used for sort
PriorityQueue<Element> pq = new PriorityQueue<Element>(arrSize);
// Put the first element of each array to the PriorityQueue
for (int i = 0; i < arrSize; i++) {
pq.offer(new Element(map.get(i)[0], i, 0));
}
Element tem = null;
int i = 1;
while ((tem = pq.poll()) != null) {
System.out.print(tem.value + "\t");
if (i % 6 == 0)
System.out.println();
i++;
// Put the next element to array if have
if (tem.whichIndex + 1 < map.get(tem.whichArray).length)
pq.offer(new Element( map.get(tem.whichArray)[tem.whichIndex + 1], tem.whichArray, tem.whichIndex + 1));
}
}
运行结果:
2 5 6 8 9 19
20 24 31 38 67 76
234 266 388 389 399 736
736 1021 3923 7136 39342
原理很简单: 先把每个数组的首元素取出来,形成一个堆结构。然后取出堆顶元素(目前的最小值),再将堆顶元素所在数组的后一个元素加入到堆中。如此循环直到所有元素被处理。
这个算法有个可以优化的地方,在从优先队列取出堆顶元素和重新加入元素这两步是可以合并的,没有合并的原因是java的PriorityQueue没有提供相应的接口。
附件是源码。
分享到:
相关推荐
算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-...
Java优先队列(PriorityQueue)示例Java开发Java经验技巧共5页.pdf.zip
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
主要介绍了java优先队列PriorityQueue中Comparator的用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
在使用java的优先队列PriorityQueue的时候,会看到这样的用法。 PriorityQueue queue = new PriorityQueue(new Comparator(){ @Override public int compare(Integer o1, Integer o2){ return o1.compareTo(o2);...
主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
优先队列的实现,简单实用,实现一个按ttl时间优先的优先队列
PriorityQueue-MEX-Matlab 优先级队列 matlab
JAVA:PriorityQueue
优先级队列头文件priorityqueue.h
PriorityQueue是Java中的一个优先级队列,它可以根据元素的优先级对元素进行排序,并且允许高效地获取和删除最高优先级的元素。
优先级队列是一种队列结构,是0个或多个元素的集合,每个元素都有一个优先权,PriorityQueue被内置于JDK中,本文就来解析Java中PriorityQueue优先级队列结构的源码及用法.
优先级队列cpp文件PriorityQueue.cpp
优先队列 优先队列的实现 课程:CS 146 数据结构和算法 圣何塞州立大学 作者:Kory Le、Megan Chan ==============
C#泛型优先队列
前面以Java ArrayDeque为例讲解了Stack和Queue,其实还有一种特殊的队列叫做PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值小的(Java的优先队列每次取小元素,C++的优先队列...
任务的优先队列 基于任务的PriorityQueue的实现在此程序中,用户可以: 注册新任务,并传递名称和优先级 提取并返回列表中优先级最低的任务 清除任务列表 列出所有待处理的任务及其优先级 导入和导出CSV文件中的...
《Java 基础核心总结》 Java 概述 什么是 Java2 Java 的特点Java 开发环境 JDK JRE Java 开发环境配置 Java 基本语法 数据类型基础语法运算符 Java 执行控制流程条件语句 if 条件语句 if...else 条件语句if...else ...
C++ 优先队列 学习和使用实例, 可直接在VC2008下编译运行。