堆在java中的应用--PriorityQueue
堆的特点
堆是一种完全二叉树的模拟,堆一般是基于数组的实现,堆分大顶堆和小顶堆,大顶堆就是堆顶是最大的数据,然后子节点总比父节点小,小顶堆则反过来。java中的优先队列就是一个小顶堆的实现。
PriorityQueue的实现
堆的操作
关于堆的操作,主要就是两个。siftUp和siftDown,一个是向上调整堆,一个是向下调整堆。调整的时候java有一个使用comparator的调整,一个没有comparator的调整,调整方法基本相似,区别只是比较的时候是否使用comparator,下面主要说不是用comparator的。调整的目的是满足堆的特点。
调整的代码比较简单,加的注释已经可以疏通逻辑了。
private void siftUpComparable(int k, E x) {
//k就是元素的位置,x就是数组中k位置上的元素
Comparable<? super E> key = (Comparable<? super E>) x;
//由于是向上调整,堆顶是没有上的,所以条件就是k>0
while (k > 0) {
//在数组中,下标(k-1)/2就是父节点的位置
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//java的实现是小顶堆,所以这里判断是父元素小于比较元素就表示堆调整完成
if (key.compareTo((E) e) >= 0)
break;
//交换
queue[k] = e;
//原来的树已经满足,被交换的节点,都满足比父节点小,比子节点大,
//由于元素交换了,说明现在的元素比较小
//得继续调整,如果还能被调整,调整换下来的元素还是比较大的
k = parent;
}
queue[k] = key;
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
//由于是向下调整,所以最后一个有子节点的节点是(len-1)/2,没有子节点的就不用调整
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
//找出两个子节点中最小的比较,因为是小顶堆
if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
//父都比子小就结束
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
//由于元素交换了,下面的树形结构也得满足结构,所以继续调整
k = child;
}
queue[k] = key;
}
很明显向上调整是有一个有条件操作,向下调整则是没有特殊调整的。所以这两个操作使用的地方也是不同的。
siftDown的应用
siftDown主要是用来堆的建立。
private void heapify() {
//所有有子节点的元素进行堆的建立
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;//这个主要是在并发操作时抛出异常的,并不是线程安全集合
E result = (E) queue[0];
//取出最后一个元素,然后被当做第一个元素,重新调整堆
E x = (E) queue[s];
queue[s] = null;
//由于原来的部分已经是堆,所以就相当于堆顶没有调整
if (s != 0)
siftDown(0, x);
return result;
}
siftUp的应用
shifUp则是在现有成堆的情况下去添加元素的。
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
//modCount是用来多线程环境下抛出异常的
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);//新元素被当在最后,开始向上调整
return true;
}
PriorityQueue的其余点
构造函数
PriorityQueue在构造函数中做了一个分类的优化
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
SortedSet本身是排序的,所以可以直接把数据拷贝到priorityqueue中。
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
//获取元素和长度
this.queue = a;
this.size = a.length;
}
PriorityQueue一般也是排序的,但是这里做了一个防备,就是对于继承PriorityQueue的部分需要另外对待。java默认没有它的子类,这里是防止开发者自己的实现,万一不是排序或者堆的情况,直接拷贝数组是有问题的。
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
//PriorityQueue的不确定子类
initFromCollection(c);
}
}
剩下的情况都是依靠initFromCollection来的。其实主要就是下面的两个步骤。
private void initFromCollection(Collection<? extends E> c) {
//拷贝数组
initElementsFromCollection(c);
//建堆
heapify();
}
初始化元素大小
现在面试有一些会问这个,所以说一下,初始化11,arrayList是10,之所以不同应该是11正好是一个满二叉树的数字。
private static final int DEFAULT_INITIAL_CAPACITY = 11;
扩容
说这个也是因为面试可能会问。原来的长度小于64,就直接涨一倍再加2,否则涨0.5倍。至于为什么非要+2,我也不清楚。除了hash结构,扩容有hash计算方便问题,剩下的还没发现扩容有什么特别的讲究。
private void grow(int minCapacity) {
int oldCapacity = queue.length;
//原来的长度小于64,就直接涨一倍再加2,否则涨0.5倍
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
堆排序
堆排序就是先建立堆,然后移除第一个数,剩下的部分继续调整堆,这样每次都是拿出剩下中最大或者最小的元素,这样就是排序了。
linux中sort函数也是堆排序的实现,而且上面有一段注释
/**
43 * sort - sort an array of elements
44 * @base: pointer to data to sort
45 * @num: number of elements
46 * @size: size of each element
47 * @cmp_func: pointer to comparison function
48 * @swap_func: pointer to swap function or NULL
49 *
50 * This function does a heapsort on the given array. You may provide a
51 * swap_func function optimized to your element type.
52 *
53 * Sorting time is O(n log n) both on average and worst-case. While
54 * qsort is about 20% faster on average, it suffers from exploitable
55 * O(n*n) worst-case behavior and extra memory requirements that make
56 * it less suitable for kernel use.
57 */
这里和快排对比说明了为什么选择堆排序。
1,时间复杂度
堆排序的平均时间复杂度为O(nlogn),最坏情况也是O(nlogn),快排的平均时间复杂度也是O(nlogn),但是最坏情况是O(n*n)。
2,空间复杂度
堆排序是O(1),快排是O(logn)。快排是递归调用,所以空间要求更多一些。
其实这样比较,感觉堆排序怎么也比快排更好,但是众所周知,快排是内排序最快,而且注释也说明平均情况下,快排是比堆排序快20%的。那问题来了,为什么会这样呢?
堆排序为什么比快排慢
首先时间复杂度的计算本身是一个忽略一些情况的估算,其实和程序执行的结果不完全一致,例如程序中有比较,交换数值的操作,但是这些并不会作为评估时间复杂度的方式,但是这些是程序执行的一个操作。时间复杂度只能保证数量级直接的比较,例如nlogn是比n*n快的,但是并不代表nlogn和nlogn的执行是一样快的。
堆排序相比快排,浪费时间的一个点就是在做无效的比较交换。例如大顶堆,最上面的元素是最大的,堆排序会把最大的拿出来,然后把当时的最后一个换上去,继续建立堆。这里有个很明显的问题,就是在一次堆建立后,从最后拿的元素没有原来堆顶下面两个元素大,那么就有很多无用的比较交换,其实本来就小,还得和大的都比较一次并且换位置。这里是堆排序的一个优化点,很多人都在这里做了优化方案。
交换次数可以通过下面这个网站对比模拟。http://sorting.at/
堆排序的应用
例如对最差时间有要求的场景,例如上面说的sort的例子
大数据量的筛选:求一亿个数字里面最小的10个数字(剑指offer题目)
推荐阅读
-
重新描述循环矩阵在KCF中的应用
-
KCF跟踪算法在Python中的应用
-
Java 8新特性探究(十三)JavaFX 8新特性以及开发2048游戏-JavaFX历史## 跟java在服务器端和web端成绩相比,桌面一直是java的软肋,于是Sun公司在2008年推出JavaFX,弥补桌面软件的缺陷,请看下图JavaFX一路走过来的改进 从上图看出,一开始推出时候,开发者需使用一种名为JavaFX Script的静态的、声明式的编程语言来开发JavaFX应用程序。因为JavaFX Script将会被编译为Java bytecode,程序员可以使用Java代码代替。 JavaFX 2.0之后的版本摒弃了JavaFX Script语言,而作为一个Java API来使用。因此使用JavaFX平台实现的应用程序将直接通过标准Java代码来实现。 JavaFX 2.0 包含非常丰富的 UI 控件、图形和多媒体特性用于简化可视化应用的开发,WebView可直接在应用中嵌入网页;另外 2.0 版本允许使用 FXML 进行 UI 定义,这是一个脚本化基于 XML 的标识语言。 从JDK 7u6开始,JavaFx就与JDK捆绑在一起了,JavaFX团队称,下一个版本将是8.0,目前所有的工作都已经围绕8.0库进行。这是因为JavaFX将捆绑在Java 8中,因此该团队决定跳过几个版本号,迎头赶上Java 8。 ##JavaFx8的新特性 ## ###全新现代主题:Modena 新的Modena主题来替换原来的Caspian主题。不过在Application的start方法中,可以通过setUserAgentStylesheet(STYLESHEET_CASPIAN)来继续使用Caspian主题。 参考http://fxexperience.com/2013/03/modena-theme-update/ ###JavaFX 3D 在JavaFX8中提供了3D图像处理API,包括Shape3D (Box, Cylinder, MeshView, Sphere子类),SubScene, Material, PickResult, LightBase (AmbientLight 和PointLight子类),SceneAntialiasing等。Camera类也得到了更新。从JavaDoc中可以找到更多信息。 ###富文本 强化了富文本的支持 ###TreeTableView ###日期控件DatePicker 增加日期控件 ###用于 CSS 结构的公共 API
-
远程访问和虚拟化串口在Linux系统中的应用
-
重写的标题:小顶堆算法在堆排序中的应用
-
java中对大顶堆和优先队列进行排序的步骤
-
Java实现大顶堆:理解大顶堆在Java中的含义
-
Java数据结构实战:堆的应用——PriorityQueue小顶堆与大顶堆翻转
-
Java中的大顶堆和小顶堆
-
常见的JAVA API在算法竞赛中的应用:PriorityQueue(优先队列)