`

PriorityQueue实现原理

阅读更多

PriorityQueue是个基于优先级堆的极大优先级队列
此队列按照在构造时所指定的顺序对元素排序,既可以根据元素的自然顺序来指定排序(参阅 Comparable),
也可以根据 Comparator 来指定
,这取决于使用哪种构造方法。优先级队列不允许 null 元素。
依靠自然排序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)。
此队列的头是按指定排序方式的最小元素。如果多个元素都是最小值,则头是其中一个元素——选择方法是任意的。
队列检索操作 poll、remove、peek 和 element 访问处于队列头的元素。
优先级队列是无界的,但是有一个内部容量,控制着用于存储队列元素的数组的大小。
它总是至少与队列的大小相同。随着不断向优先级队列添加元素,其容量会自动增加。无需指定容量增加策略的细节。
注意1:该队列是用数组实现,但是数组大小可以动态增加,容量无限
注意2:此实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表, 则这些线程不应同时访问 PriorityQueue 实例,这时请使用线程安全的PriorityBlockingQueue 类
注意3:不允许使用 null 元素
注意4:此实现为插入方法(offer、poll、remove() 和 add 方法)提供 O(log(n)) 时间;
 为 remove(Object) 和 contains(Object) 方法提供线性时间;
 为检索方法(peek、element 和 size)提供固定时间。
注意5:方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素
至于原因可参考下面关于PriorityQueue的内部实现
如果需要按顺序遍历,请考虑使用 Arrays.sort(pq.toArray())。
注意6可以在构造函数中指定如何排序。如:
PriorityQueue()
          使用默认的初始容量(11)创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity)
          使用指定的初始容量创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
          使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器comparator来排序其元素。
注意7:此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。
PriorityQueue的内部实现
PriorityQueue对元素采用的是堆排序,头是按指定排序方式的最小元素。堆排序只能保证根是最大(最小),整个堆并不是有序的。

方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的
实例1的结果也正好与此相符。
实例1:
     public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("dog");
        pq.add("apple");
        pq.add("fox");
        pq.add("easy");
        pq.add("boy");
        
        while (!pq.isEmpty()) {
         System.out.print("left:");
            for (String s : pq) {
                System.out.print(s + " ");
            }
            System.out.println();
            System.out.println("poll(): " + pq.poll());
        }
    }
输出的结果如下: 
left:apple boy fox easy dog 
poll(): apple
left:boy dog fox easy 
poll(): boy
left:dog easy fox 
poll(): dog
left:easy fox 
poll(): easy
left:fox 
poll(): fox
可以看到,虽然PriorityQueue保持了队列顶部元素总是最小,但内部的其它元素的顺序却随着元素的减少始终处于变化之中
察看源代码来一探究竟。从Netbeans中非常方便的连接到PriorityQueue的add函数实现,
最终跟踪到函数private void siftUpComparable(int k, E 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;
    }
相对于add的操作,该函数的入口参数k是指新加入元素的下标,而x 就是新加入的元素。
乍一看,这个函数的实现比较令人费解,尤其是parent的定义。通过进一步分析了解到,
PriorityQueue内部成员数组 queue其实是实现了一个二叉树的数据结构,这棵二叉树的根节点是queue[0],
左子节点是queue[1],右子节点是queue[2],而 queue[3]又是queue[1]的左子节点,依此类推,给定元素queue
该节点的父节点是queue[(i-1)/2]。因此 parent变量就是对应于下标为k的节点的父节点。
弄清楚了这个用数组表示的二叉树,就可以理解上面的代码中while 循环进行的工作是,
当欲加入的元素小于其父节点时,就将两个节点的位置交换。这个算法保证了如果只执行add操作,那么queue这个二叉树是有序的:
该二叉树中的任意一个节点都小于以该节点为根节点的子数中的任意其它节点。这也就保证了queue[0],即队顶元素总是所有元素中最小的。
需要注意的是,这种算法无法保证不同子树上的两个节点之间的大小关系。举例来说,queue[3]一定会小于queue[7],但是未必会小于queue[9],因为queue[9]不在以queue[3]为根节点的子树上。
弄清楚了add的操作,那么当队列中的元素有变化的时候,对应的数组queue又该如何变化呢?察看函数poll(),
最终追中到函数private E removeAt(int i),代码如下:
     private E removeAt(int i) {
        assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i) // removed last element
            queue = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue
 == moved) {
                siftUp(i, moved);
                if (queue
 != moved)
                    return moved;
            }
        }
        return null;
    }

这个函数的实现方法是,将队尾元素取出,插入到位置i,替代被删除的元素,然后做相应的调整,保证二叉树的有序,
即任意节点都是以它为根节点的子树中的最小节点。进一步的代码就留给有兴趣的读者自行分析,
要说明的是,对于 queue这样的二叉树结构有一个特性,即如果数组的长度为length,
那么所有下标大于length/2的节点都是叶子节点,其它的节点都有子节点。
总结:可以看到这种算法的实现,充分利用了树结构在搜索操作时的优势,效率又高于维护一个全部有序的队列

分享到:
评论

相关推荐

    Java的优先队列PriorityQueue原理及实例分析

    Java 的优先队列 PriorityQueue 原理及实例分析 Java 的优先队列 PriorityQueue 是 Queue 接口的实现,可以对其中元素进行排序,可以放基本数据类型的包装类(如:Integer,Long 等)或自定义的类。PriorityQueue ...

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

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

    C++ 优先队列实例(Priority_queue)

    首先,C++标准库提供了`&lt;queue&gt;`和`&lt;priority_queue&gt;`头文件,用于实现常规队列和优先队列。优先队列不像普通队列那样遵循先进先出(FIFO)原则,而是根据元素的优先级决定哪个元素先出队。优先级高的元素会优先处理...

    JDK源码之PriorityQueue解析

    二、优先队列的实现原理 优先队列的实现方式是使用二叉堆的结构,需要满足以下两条性质:(1)任何结点的值都小于或等于其子节点的值;(2)所有结点从上到下,从左到右填入,即一棵完全二叉树。基于这两条规律,...

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

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

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

    PriorityQueue在JDK中内置,基于二叉堆数据结构实现,特别是最小堆,这意味着队列头部的元素总是具有最低的优先级。在Java 7中,PriorityQueue的底层实现是一个近似完全二叉树的数组,保证了队列的高效操作。 ...

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

    理解`Comparator`的工作原理以及如何在`PriorityQueue`中使用它,可以帮助我们更有效地利用这个数据结构来满足特定的排序需求。在实际编程中,`PriorityQueue`结合`Comparator`可以广泛应用于需要优先级处理任务、...

    数据结构的原理及其java实现

    本篇文档将深入探讨数据结构的基本原理及其在Java中的实现方式。 一、数组 数组是最基础的数据结构,它是一系列相同类型元素的集合,通过索引进行访问。在Java中,数组可以通过声明数组变量并初始化来创建,例如: ...

    PriorityQueue:优先队列的实现

    在CS 146 数据结构和算法课程中,会深入讲解优先队列的原理以及如何在Java中高效地使用`PriorityQueue`。通过学习,学生可以理解二叉堆的内部工作机制,掌握如何插入、删除和查询优先级元素,以及如何根据需求自定义...

    java使用小根堆实现优先级队列的几种方式

    本篇文章将探讨如何使用小根堆来实现Java中的优先级队列,以及其背后的实现原理和不同方法。 1. 小根堆的概念: 小根堆是二叉堆的一种类型,其中每个父节点的值都小于或等于其子节点的值。在Java中,`...

    keap:Keap是一种堆数据结构,具有稳定的PriorityQueue和稳定的Keapsort排序算法

    Keap是一种特殊的堆数据结构,它的设计目标是提供稳定的优先级队列(PriorityQueue)功能以及稳定的...对于Kotlin开发者来说,了解并掌握Keap堆的原理和实现,不仅能提升编程技能,还能为解决复杂问题提供新的思路。

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

    2. **堆的实现原理**: - **数组存储**:由于堆是一种树形结构,但为了节省空间,通常用一维数组来表示。数组的索引可以映射到堆的层级关系,例如,索引i的父节点索引为(i-1)/2,左孩子索引为2*i+1,右孩子索引为2*...

    优先队列算法实现(Java)

    本实现是用Java编程语言完成的,Java提供了一个内置的PriorityQueue类,但这里可能是自定义实现,以便更好地理解其工作原理和优化。 1. **优先队列的基本概念** - 优先队列是一个队列,但它不同于普通的FIFO(先进...

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

    这篇文章将探讨如何利用数组实现优先队列,并通过提供的`PriorityQ.java`文件来深入理解其实现原理。 1. **优先队列基本概念** 优先队列是一种数据结构,它维护了一个有序的队列,通常按照优先级的高低进行排序。...

    时间轮定时器java实现

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

    八大排序算法总结(含Java实现源代码)

    这里我们将深入探讨八大排序算法,并结合Java语言来理解它们的实现原理。 1. 冒泡排序(Bubble Sort) 冒泡排序是一种简单的交换式排序算法。它通过重复遍历待排序的元素列表,比较相邻元素并根据需要交换它们,...

    详解Java阻塞队列(BlockingQueue)的实现原理

    "详解Java阻塞队列(BlockingQueue)的实现原理" Java阻塞队列(BlockingQueue)是Java.util.concurrent包下重要的数据结构,提供了线程安全的队列访问方式。BlockingQueue的实现原理主要是基于四组不同的方法用于...

    基于Dijkstra路由算法的路由软件实现

    在本文中,我们将深入探讨Dijkstra算法的原理、Java实现及其在路由软件中的应用。 **一、Dijkstra算法的基本原理** Dijkstra算法的主要目标是找到图中节点间的最短路径。它采用贪心策略,每次迭代都会找到当前未...

    C#泛型优先队列

    **优先队列的实现原理** 优先队列通常用二叉堆来实现,即每个父节点的值都大于或等于其子节点的值(最大堆)或小于或等于其子节点的值(最小堆)。在C#中,`System.Collections.Generic`命名空间下的`PriorityQueue`...

    Haffman哈弗曼编码的Matlab实现

    首先,我们需要理解哈弗曼编码的基本原理。哈弗曼编码是通过构建哈弗曼树(也称为最优二叉树)来实现的。这种树的特点是:频率高的字符对应的路径较短,频率低的字符对应的路径较长。这样,频繁出现的字符在编码时...

Global site tag (gtag.js) - Google Analytics