`
zhangxiong0301
  • 浏览: 359651 次
社区版块
存档分类
最新评论

java中priorityQueue的实现

    博客分类:
  • JAVA
 
阅读更多

PriorityQueue介绍

    在平时的编程工作中似乎很少碰到PriorityQueue(优先队列) ,故很多人一开始看到优先队列的时候还会有点迷惑。优先队列本质上就是一个最小堆。前面一篇文章介绍了堆排序和堆的性质。而堆又是什么呢?它是一个数组,不过满足一个特殊的性质。我们以一种完全二叉树的视角去看这个数组,并用二叉树的上下级关系来映射到数组上面。如果是最大堆,则二叉树的顶点是保存的最大值,最小堆则保存的最小值。

    下面是一个典型的优先队列的结构图:

 

    它的每个父节点都比两个子节点要小,但是整个数组又不是完全顺序的。

    有了前面的这些铺垫,我们再来看它的整体结构和各种调整过程。

建堆

   PriorityQueue内部的数组声明如下:

Java代码  收藏代码
  1. private transient Object[] queue;  
  2.   
  3. private static final int DEFAULT_INITIAL_CAPACITY = 11;  

   它默认的长度为11. 建堆的过程中需要添加新的元素,

    PriorityQueue的建堆过程和最大堆的建堆过程基本上一样的,从有子节点的最靠后元素开始往前,每次都调用siftDown方法来调整。这个过程也叫做heapify。

 

Java代码  收藏代码
  1. private void heapify() {  
  2.         for (int i = (size >>> 1) - 1; i >= 0; i--)  
  3.             siftDown(i, (E) queue[i]);  
  4.     }  
  5.   
  6. private void siftDown(int k, E x) {  
  7.         if (comparator != null)  
  8.             siftDownUsingComparator(k, x);  
  9.         else  
  10.             siftDownComparable(k, x);  
  11.     }  
  12.   
  13. private void siftDownComparable(int k, E x) {  
  14.         Comparable<? super E> key = (Comparable<? super E>)x;  
  15.         int half = size >>> 1;        // loop while a non-leaf  
  16.         while (k < half) {  
  17.             int child = (k << 1) + 1// assume left child is least  
  18.             Object c = queue[child];  
  19.             int right = child + 1;  
  20.             if (right < size &&  
  21.                 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)  
  22.                 c = queue[child = right];  
  23.             if (key.compareTo((E) c) <= 0)  
  24.                 break;  
  25.             queue[k] = c;  
  26.             k = child;  
  27.         }  
  28.         queue[k] = key;  
  29.     }  
  30.   
  31.     private void siftDownUsingComparator(int k, E x) {  
  32.         int half = size >>> 1;  
  33.         while (k < half) {  
  34.             int child = (k << 1) + 1;  
  35.             Object c = queue[child];  
  36.             int right = child + 1;  
  37.             if (right < size &&  
  38.                 comparator.compare((E) c, (E) queue[right]) > 0)  
  39.                 c = queue[child = right];  
  40.             if (comparator.compare(x, (E) c) <= 0)  
  41.                 break;  
  42.             queue[k] = c;  
  43.             k = child;  
  44.         }  
  45.         queue[k] = x;  
  46.     }  

    siftDown的过程是将一个节点和它的子节点进行比较调整,保证它比它所有的子节点都要小。这个调整的顺序是从当前节点向下,一直调整到叶节点。

 

    siftDown的过程如下图所示:

    因为一开始要建堆的时候,里面的元素是杂乱无章的,所以调整前可能的结构如下:

    假设我们siftDown的元素是9,则它先和它的左右子节点进行比较,然后和最小的子节点交换位置:

 

    经过一次交换之后,发现它还有子节点,而且子节点比它小,所以需要继续交换。

    按照这个思路来理解,前面的过程就很明了了。

扩展

    堆里面的数组长度不是固定不变的,如果不断往里面添加新元素的时候,也会面临数组空间不够的情形,所以也需要对数组长度进行扩展。这个扩展方法的源头就是由插入元素引起的。

数组长度扩展的方法如下:

Java代码  收藏代码
  1. private void grow(int minCapacity) {  
  2.         int oldCapacity = queue.length;  
  3.         // Double size if small; else grow by 50%  
  4.         int newCapacity = oldCapacity + ((oldCapacity < 64) ?  
  5.                                          (oldCapacity + 2) :  
  6.                                          (oldCapacity >> 1));  
  7.         // overflow-conscious code  
  8.         if (newCapacity - MAX_ARRAY_SIZE > 0)  
  9.             newCapacity = hugeCapacity(minCapacity);  
  10.         queue = Arrays.copyOf(queue, newCapacity);  
  11.     }  
  12.   
  13.     private static int hugeCapacity(int minCapacity) {  
  14.         if (minCapacity < 0// overflow  
  15.             throw new OutOfMemoryError();  
  16.         return (minCapacity > MAX_ARRAY_SIZE) ?  
  17.             Integer.MAX_VALUE :  
  18.             MAX_ARRAY_SIZE;  
  19.     }  

    这部分代码和ArrayList的内部实现代码基本相同,都是先找到合适的数组长度,然后将元素从旧的数组拷贝到新的数组。

    而添加新元素的过程如下:

Java代码  收藏代码
  1. public boolean offer(E e) {  
  2.         if (e == null)  
  3.             throw new NullPointerException();  
  4.         modCount++;  
  5.         int i = size;  
  6.         if (i >= queue.length)  
  7.             grow(i + 1);  
  8.         size = i + 1;  
  9.         if (i == 0)  
  10.             queue[0] = e;  
  11.         else  
  12.             siftUp(i, e);  
  13.         return true;  
  14.     }  

    每次添加新的元素进来实际上是在数组的最后面增加。在增加这个元素的时候就有了判断数组长度和调整的一系列动作。等这些动作调整完之后就要进行siftUp方法调整。这样做是为了保证堆原来的性质。

    siftUp的过程可以用如下图来描述:

    假设我们在后面添加了元素3,那么我们就要将这个元素和它的父节点比较,如果它比它的父节点小,则要交换他们的顺序。这样一直重复到它大于等于它的父节点或者到根节点。

    经过调整之后,则变成符合条件的最小堆:‘

     它的详细实现代码如下:

Java代码  收藏代码
  1. private void siftUp(int k, E x) {  
  2.         if (comparator != null)  
  3.             siftUpUsingComparator(k, x);  
  4.         else  
  5.             siftUpComparable(k, x);  
  6.     }  
  7.   
  8.     private void siftUpComparable(int k, E x) {  
  9.         Comparable<? super E> key = (Comparable<? super E>) x;  
  10.         while (k > 0) {  
  11.             int parent = (k - 1) >>> 1;  
  12.             Object e = queue[parent];  
  13.             if (key.compareTo((E) e) >= 0)  
  14.                 break;  
  15.             queue[k] = e;  
  16.             k = parent;  
  17.         }  
  18.         queue[k] = key;  
  19.     }  
  20.   
  21.     private void siftUpUsingComparator(int k, E x) {  
  22.         while (k > 0) {  
  23.             int parent = (k - 1) >>> 1;  
  24.             Object e = queue[parent];  
  25.             if (comparator.compare(x, (E) e) >= 0)  
  26.                 break;  
  27.             queue[k] = e;  
  28.             k = parent;  
  29.         }  
  30.         queue[k] = x;  
  31.     }  

注意事项:

    我们看前面的调整方法不管是siftUp还是siftDown都用了两个方法,一个是用的comparator,还有一个是用的默认比较结果。这样做的目的是考虑到我们要比较的元素不仅仅是数字等类型,也有可能是被定义了可比较的数据类型。对于自定义的数据类型,他们的大小比较定义需要实现comparator接口。至于使用comparator接口的意义背后的思想,可以参照我的这一篇博文

 

实例

PriorityQueue这种数据结构支持按照优先级取出里面的元素。这是和其它常用数据结构,比如 ArrayList, Queue, Stack等最大的区别。因为要支持优先级,而heap具有类似的结构,所以,PriorityQueue一般都是基于HEAP实现的。(也可以用其它数据结构实现,但是各种复杂度会有不同。)

基于HEAP实现的PriorityQueue复杂度分析:

add(E e): O(lg n)

poll():  O(lg n) (注意,取出元素只需要O(1), 但是维护HEAP结构需要 O(lg n))

remove(E e): O(n)

下面例子是用Priority Queue保存学生信息,学生类含有姓名和成绩,当把学生保存在Priority Queue里时,成绩最低的学生放在最前面。如果想把成绩最高的放在最前面,只要把compare方法改成 return s2.grade - s1.grade; 即可。

[java] view plaincopy
 
  1. import java.util.Comparator;  
  2. import java.util.PriorityQueue;  
  3. import java.util.Random;  
  4.   
  5. public class PriorityQueueTutorial{  
  6.       
  7.     public static void main(String args[]){  
  8.         PriorityQueue<Student> queue = new PriorityQueue<Student>(11,  
  9.                 new Comparator<Student>() {  
  10.                   public int compare(Student s1, Student s2) {  
  11.                     return s1.grade - s2.grade;  
  12.                   }  
  13.                 });       
  14.               
  15.         for (int i = 1; i <= 100; i++) {  
  16.             queue.add(new Student("s" + i, (new Random().nextInt(1000))));  
  17.         }  
  18.         while (!queue.isEmpty()) {  
  19.               System.out.println(queue.poll().toString());  
  20.         }  
  21.     }  
  22. }  
  23.   
  24. class Student {   
  25.     String name;  
  26.     int grade;  
  27.     public Student(String name, int grade)  
  28.     {  
  29.         this.name = name;  
  30.         this.grade = grade;  
  31.     }  
  32.       
  33.     public String toString() {  
  34.         return name + " " + grade;  
  35.     }  
  36. }  

 

总结

    PriorityQueue本质上就是堆排序里面建的最小堆。最小堆满足的一个基本性质是堆顶端的元素是所有元素里最小的那个。如果我们将顶端的元素去掉之后,为了保持堆的性质,需要进行调整。对堆的操作和调整主要包含三个方面,增加新的元素,删除顶端元素和建堆时保证堆性质的操作。前面讨论堆排序的文章已经有了一个详细的介绍。这里主要结合jdk的类库实现,看看一个用于实际生产环境的优先队列实现。 另外,PriorityQueue在一些经典算法中也有得到应用,相当于是它们实现的基础。

参考材料

 http://shmilyaw-hotmail-com.iteye.com/blog/1775868

分享到:
评论

相关推荐

    JAVA:PriorityQueue

    ### Java中的PriorityQueue详解 #### 类概述 `PriorityQueue`是Java集合框架的一部分,它是一个基于优先级堆的无界优先级队列。这个队列的元素可以按照它们的自然顺序或者是通过构造队列时提供的`Comparator`进行...

    解析Java中PriorityQueue优先级队列结构的源码及用法

    在Java 7中,PriorityQueue的底层实现是一个近似完全二叉树的数组,保证了队列的高效操作。 优先级队列的核心特性包括: 1. **数据结构**:PriorityQueue使用二叉堆作为其数据结构,通常是一个最小堆,保证队头元素...

    Java集合框架源码剖析:PriorityQueue

    总体介绍  前面以Java ArrayDeque为例讲解了Stack和Queue,其实还有一种特殊的队列叫做...  Java中PriorityQueue实现了Queue接口,不允许放入null元素;其通过堆实现,具体说是通过完全二叉树(complete bin

    Java优先队列(PriorityQueue)示例Java

    Java的优先队列(PriorityQueue)是Java集合框架中一个重要的数据结构,它是一个基于堆实现的无界队列。优先队列中的元素按照优先级排序,最高的优先级元素总是在队列的头部。在Java中,PriorityQueue类位于`java....

    基于java优先队列(PriorityQueue)的多路排序算法(含代码)

    在Java中,`PriorityQueue`实现了`Queue`接口,并且其元素按照自然顺序或者由比较器提供的顺序进行排序。当我们需要合并多个已排序的输入流时,我们可以将每个输入流的头部元素(即最小的元素)添加到优先队列中。...

    java优先队列PriorityQueue中Comparator的用法详解

    在Java编程中,`PriorityQueue` 是一个基于优先堆的无界队列。它按照特定的顺序(默认是最小优先顺序)来处理元素,允许快速访问队列头部的最小元素。当我们需要自定义排序规则时,可以使用`Comparator`接口。本文将...

    A*算法Java/C++实现

    在Java实现中,可以使用PriorityQueue作为开放列表,利用优先级队列自动按f(n)排序。C++中可以使用优先级队列库(和)来达到相同效果。同时,需要注意在更新相邻节点时避免无限循环,可以通过在节点上添加父节点引用...

    8种常用排序方法java类实现

    Java实现中,可以使用两层循环结构,外层控制遍历次数,内层负责比较和交换。 2. **选择排序(Selection Sort)**:选择排序每次找出未排序部分的最大(或最小)元素,放置到已排序部分的末尾。Java中,用一个临时...

    时间轮定时器java实现

    在Java中,我们可以利用`PriorityQueue`类来实现最小堆。这种定时器的工作原理是将待执行的任务插入到堆中,堆顶的任务即为最早需要执行的任务。每次需要触发定时事件时,就删除堆顶的任务并执行。这种实现方式高效...

    Lists_Stack_Queue_PriorityQueue.java

    - **实现**:Java的`PriorityQueue`使用堆数据结构实现,提供`offer`、`poll`等方法,并保证每次取出的都是当前队列中优先级最高的元素。 - **特性**:默认按照自然顺序或自定义比较器进行排序,不允许插入null,...

    Java实现堆并调整

    在Java中实现堆,我们通常会用到`ArrayList`或者`ArrayDeque`类,但更常见的是使用`PriorityQueue`,它是一个基于优先堆的无界队列。 在给定的文件中,我们有两个类:`Heapest.java`和`HeapOperator.java`。`...

    优先队列算法实现(Java)

    综上所述,优先队列是算法设计中的重要工具,Java中的PriorityQueue类提供了方便的接口,但自定义实现有助于深入理解和优化。在实际应用中,理解其内部工作机制以及如何适配具体需求是非常关键的。通过阅读和分析...

    java实现数据结构

    Java的`PriorityQueue`类实现了这个概念,元素按照其自然顺序或自定义比较器进行排序。`offer()`方法添加元素,`poll()`移除并返回最高优先级元素,`peek()`查看但不移除。 最后,哈希表,也称为散列表,提供快速的...

    JAVA基本5种数据结构的实现。

    虽然这里没有明确的堆实现文件,但Java提供了`java.util.PriorityQueue`来实现堆数据结构。 在实际编程中,这些数据结构的选择取决于特定的需求,例如快速访问、高效的插入和删除等。理解并熟练使用这些数据结构...

    用java通过文件操作实现最短路径问题

    在Java中,我们可以使用优先队列(PriorityQueue)来存储待处理节点,从而高效地找到下一个最近的节点。 2. **Floyd-Warshall算法**:该算法使用动态规划,通过迭代逐步更新所有节点对之间的最短路径。对于每一对...

    Java-PriorityQueue:任务优先级队列的实现

    基于任务的PriorityQueue的实现在此程序中,用户可以: 注册新任务,并传递名称和优先级 提取并返回列表中优先级最低的任务 清除任务列表 列出所有待处理的任务及其优先级 导入和导出CSV文件中的任务列表 退出该...

    用数组实现的优先队列(JAVA)

    在Java中,我们可以使用`java.util.PriorityQueue`类来实现优先队列,但这里我们关注的是用数组实现的方法。 2. **数组实现的基本思想** 数组实现优先队列的核心思想是维护一个最小堆(最小堆是堆数据结构的一种,...

    用堆实现简单的优先队列(JAVA)

    在Java中,我们可以利用堆(Heap)来实现一个简单的优先队列。堆是一种二叉树形数据结构,其每个父节点的值都大于或等于其子节点的值,这样的结构被称为最大堆。 在给定的文件中,我们有两个文件:PriorityQueue....

    进程调度的两种算法JAVA实现----FCFS(先来先服务)和SJF(最短作业优先)

    在操作系统中,进程调度是管理CPU执行权分配的关键机制,其目标是确保系统资源的高效利用和公平性。本文将详细介绍两种经典的进程调度算法...在JAVA中实现这些算法,可以帮助我们更好地理解和模拟操作系统的调度行为。

    PriorityQueue:使用 O(LogN) 复杂度为测试类实现 PriorityQueue

    在Java中,PriorityQueue类实现了Queue接口,它遵循最小堆的原理,即队首元素总是队中最小的(默认情况下)。在本项目中,我们将探讨如何使用O(LogN)的时间复杂度来实现PriorityQueue,并理解其内部工作原理。 首先...

Global site tag (gtag.js) - Google Analytics