PriorityQueue介绍
在平时的编程工作中似乎很少碰到PriorityQueue(优先队列) ,故很多人一开始看到优先队列的时候还会有点迷惑。优先队列本质上就是一个最小堆。前面一篇文章介绍了堆排序和堆的性质。而堆又是什么呢?它是一个数组,不过满足一个特殊的性质。我们以一种完全二叉树的视角去看这个数组,并用二叉树的上下级关系来映射到数组上面。如果是最大堆,则二叉树的顶点是保存的最大值,最小堆则保存的最小值。
下面是一个典型的优先队列的结构图:
它的每个父节点都比两个子节点要小,但是整个数组又不是完全顺序的。
有了前面的这些铺垫,我们再来看它的整体结构和各种调整过程。
建堆
PriorityQueue内部的数组声明如下:
private transient Object[] queue; private static final int DEFAULT_INITIAL_CAPACITY = 11;
它默认的长度为11. 建堆的过程中需要添加新的元素,
PriorityQueue的建堆过程和最大堆的建堆过程基本上一样的,从有子节点的最靠后元素开始往前,每次都调用siftDown方法来调整。这个过程也叫做heapify。
private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); } private void siftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); } private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least 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; } private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; while (k < half) { int child = (k << 1) + 1; Object c = queue[child]; int right = child + 1; if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; if (comparator.compare(x, (E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = x; }siftDown的过程是将一个节点和它的子节点进行比较调整,保证它比它所有的子节点都要小。这个调整的顺序是从当前节点向下,一直调整到叶节点。
siftDown的过程如下图所示:
因为一开始要建堆的时候,里面的元素是杂乱无章的,所以调整前可能的结构如下:
假设我们siftDown的元素是9,则它先和它的左右子节点进行比较,然后和最小的子节点交换位置:
经过一次交换之后,发现它还有子节点,而且子节点比它小,所以需要继续交换。
按照这个思路来理解,前面的过程就很明了了。
扩展
堆里面的数组长度不是固定不变的,如果不断往里面添加新元素的时候,也会面临数组空间不够的情形,所以也需要对数组长度进行扩展。这个扩展方法的源头就是由插入元素引起的。
数组长度扩展的方法如下:
private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
这部分代码和ArrayList的内部实现代码基本相同,都是先找到合适的数组长度,然后将元素从旧的数组拷贝到新的数组。
而添加新元素的过程如下:
public boolean offer(E e) { if (e == null) throw new NullPointerException(); 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; }
每次添加新的元素进来实际上是在数组的最后面增加。在增加这个元素的时候就有了判断数组长度和调整的一系列动作。等这些动作调整完之后就要进行siftUp方法调整。这样做是为了保证堆原来的性质。
siftUp的过程可以用如下图来描述:
假设我们在后面添加了元素3,那么我们就要将这个元素和它的父节点比较,如果它比它的父节点小,则要交换他们的顺序。这样一直重复到它大于等于它的父节点或者到根节点。
经过调整之后,则变成符合条件的最小堆:‘
它的详细实现代码如下:
private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; }
注意事项:
我们看前面的调整方法不管是siftUp还是siftDown都用了两个方法,一个是用的comparator,还有一个是用的默认比较结果。这样做的目的是考虑到我们要比较的元素不仅仅是数字等类型,也有可能是被定义了可比较的数据类型。对于自定义的数据类型,他们的大小比较定义需要实现comparator接口。至于使用comparator接口的意义背后的思想,可以参照我的这一篇博文。
总结
PriorityQueue本质上就是堆排序里面建的最小堆。最小堆满足的一个基本性质是堆顶端的元素是所有元素里最小的那个。如果我们将顶端的元素去掉之后,为了保持堆的性质,需要进行调整。对堆的操作和调整主要包含三个方面,增加新的元素,删除顶端元素和建堆时保证堆性质的操作。前面讨论堆排序的文章已经有了一个详细的介绍。这里主要结合jdk的类库实现,看看一个用于实际生产环境的优先队列实现。 另外,PriorityQueue在一些经典算法中也有得到应用,相当于是它们实现的基础。
相关推荐
JAVA:PriorityQueue
PriorityQueue是Java中的一个优先级队列,它可以根据元素的优先级对元素进行排序,并且允许高效地获取和删除最高优先级的元素。
前面以Java ArrayDeque为例讲解了Stack和Queue,其实还有一种特殊的队列叫做PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值小的(Java的优先队列每次取小元素,C++的优先队列...
Java优先队列(PriorityQueue)示例Java开发Java经验技巧共5页.pdf.zip
以下是一些 Java 集合方面的面试题: Java 中集合框架的主要接口是什么? ArrayList 和 LinkedList 有什么区别? HashSet 和 TreeSet 有什么区别? HashMap 和 TreeMap 有什么区别? 什么是迭代器?如何使用它来遍历...
NULL 博文链接:https://robblog.iteye.com/blog/566114
Lists_Stack_Queue_PriorityQueue.java
主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
优先级队列是一种队列结构,是0个或多个元素的集合,每个元素都有一个优先权,PriorityQueue被内置于JDK中,本文就来解析Java中PriorityQueue优先级队列结构的源码及用法.
优先队列使用 O(LogN) 复杂度为测试类实现 PriorityQueue。
1) 掌握Java集合框架的概念以及几种具体实现:ArrayList, LinkedList, HashSet, TreeSet, PriorityQueue; 2) 掌握Java集合框架的映射的概念以及映射的两种基本实现:HashMap,TreeMap; 3)掌握枚举类型以及枚举集...
主要介绍了java优先队列PriorityQueue中Comparator的用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
Collections 类集合实现类特征图 泛形 泛型的使用 用泛型表示类 用泛型表示接口泛型方法 泛型通配符 反射 Class 类Field 类Method 类ClassLoader 类 枚举 枚举特性 枚举和普通类-样枚举神秘之处 枚举类 I/O File...
优先级队列头文件priorityqueue.h
主要为大家详细介绍了JDK源码之PriorityQueue,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Java核心类 字符串和编码 StringBuilder StringJoiner 包装类型 JavaBean 枚举类 BigInteger BigDecimal 常用工具类 异常处理 Java的异常 捕获异常 抛出异常 自定义异常 使用断言 使用JDK Logging ...
PriorityQueue-MEX-Matlab 优先级队列 matlab
7.5.2 PriorityQueue实现类 269 7.6 Map 270 7.6.1 HashMap和Hashtable实现类 271 7.6.2 SortedMap接口和TreeMap实现类 276 7.6.3 WeakHashMap实现类 279 7.6.4 IdentityHashMap实现类 280 7.6.5 EnumMap实现...
• 抽象的针对不同Java集合实现的比较实验,以找出时间与集合大小之间的关系,以及在检索过程中,从集合中删除元素以及遍历每个集合中的所有元素的过程。 • 方法用数字填充集合,并测量进行散文的时间,然后将结果...
在使用java的优先队列PriorityQueue的时候,会看到这样的用法。 PriorityQueue queue = new PriorityQueue(new Comparator(){ @Override public int compare(Integer o1, Integer o2){ return o1.compareTo(o2);...