Java PriorityQueue数据结构接口原理及用法

PriorityQueue是从JDK1.5开始提供的新的数据结构接口，它是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列（参阅 Comparable），也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）

优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节

简单应用：

package test;
import java.util.PriorityQueue;
public class PriorityQueueTest1 {
 @SuppressWarnings("unchecked")
 public static void main(String[] args) {
 PriorityQueue queue = new PriorityQueue();
 queue.add("AAAAA"); // Add接受的参数是Obj，PriorityQueue使用integer String等基本的数据类型时，默认new时有参数，如果不写则是按照默认排序
 queue.add("BBBBB");
 queue.add("CCCCC");
 queue.add("DDDDD"); 

 System.out.println(queue.peek()); // 获取但不移除此队列的头
 System.out.println(queue.poll()); // 获取并移除此队列的头
 System.out.println(queue.poll());

 queue.offer("ZZZZZ"); // 将指定的元素插入此优先级队列

 System.out.println(queue.poll());
 System.out.println(queue.poll());
 System.out.println(queue.poll());

 System.out.println(queue.poll()); // 到这里已经没有元素，打印Null
 }
}

定义比较器：

package test;
import java.util.Comparator;
import java.util.PriorityQueue;
@SuppressWarnings("unchecked")
public class PriorityQueueTest2 {
 private static PriorityQueue queue = new PriorityQueue(10,new Comparators());
 public static void main(String[] args) {
 QueueObject queueObject = new QueueObject();
 queueObject.setId(4);
 queueObject.setObject("AAAAA");
 queue.add(queueObject);
 QueueObject queueObject1 = new QueueObject();
 queueObject1.setId(1);
 queueObject1.setObject("BBBBB");
 queue.add(queueObject1);
 QueueObject queueObject2 = new QueueObject();
 queueObject2.setId(3);
 queueObject2.setObject("CCCCC");
 queue.add(queueObject2);

 System.out.println(((QueueObject)queue.poll()).getObject());
 System.out.println(((QueueObject)queue.poll()).getObject());
 System.out.println(((QueueObject)queue.poll()).getObject());
 }
}
class QueueObject {
  private int id;
  private Object object;
  public int getId() {
    return id;
  }
  public void setId(int id) {
    this.id = id;
  }
  public Object getObject() {
    return object;
  }
  public void setObject(Object object) {
    this.object = object;
  }
}
@SuppressWarnings("unchecked")
class Comparators implements Comparator{
  public int compare(Object arg0, Object arg1) {
    int val1 = ((QueueObject)arg0).getId();
    int val2 = ((QueueObject)arg1).getId();
    return val1 < val2 ? 0 : 1;
  }
}

注意事项：

注意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 comparator)
  • 使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。

注意7:此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。

PriorityQueue的内部实现

PriorityQueue对元素采用的是堆排序，头是按指定排序方式的最小元素。堆排序只能保证根是最大（最小），整个堆并不是有序的。

方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 优先队列(priority_queue)的C语言实现代码

    优先队列(priority_queue)和一般队列(queue)的函数接口一致,不同的是,优先队列每次出列的是整个队列中最小(或者最大)的元素. 本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下: 一.键值对结构体:KeyValue 复制代码 代码如下: // =============KeyValue Struct==================================typedef struct key_value_struct KeyValu

  • C++线程优先级SetThreadPriority的使用实例

    本文实例讲述了C++线程优先级SetThreadPriority的使用方法,分享给大家供大家参考.具体方法如下: 复制代码 代码如下: // ThreadPriority.cpp : 定义控制台应用程序的入口点.  //    #include "stdafx.h"  #include <Windows.h>    DWORD WINAPI ThreadProcIdle(LPVOID lpParameter)  {      for (int i=0;i<20;i++

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

    这篇文章主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.优先队列概述 优先队列PriorityQueue是Queue接口的实现,可以对其中元素进行排序, 可以放基本数据类型的包装类(如:Integer,Long等)或自定义的类 对于基本数据类型的包装器类,优先队列中元素默认排列顺序是升序排列 但对于自己定义的类来说,需要自己定义比较器 二.常用方法 peek()//返回队首元素

  • Java优先队列(PriorityQueue)重写compare操作

    we can custom min heap or max heap by override the method compare. package myapp.kit.quickstart.utils; import java.util.Comparator; import java.util.Queue; /** * priority queue (heap) demo. * * @author huangdingsheng * @version 1.0, 2020/5/8 */ publi

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

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

    一.PriorityQueue的数据结构 JDK7中PriorityQueue(优先级队列)的数据结构是二叉堆.准确的说是一个最小堆. 二叉堆是一个特殊的堆, 它近似完全二叉树.二叉堆满足特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆. 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆. 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆. 下图是一个最大堆 priorityQueue队头就是给定顺序的最小元素. prio

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

    在使用java的优先队列PriorityQueue的时候,会看到这样的用法. PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2){ return o1.compareTo(o2); } }); 那这样到底构造的是最大优先还是最小优先队列呢? 看看源码

  • PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例

    PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例

    队列这种数据结构更简单,就像我们生活中排队一样,它的特性是先进先出(FIFO). PHP SPL中SplQueue类就是实现队列操作,和栈一样,它也可以继承双链表(SplDoublyLinkedList)轻松实现. SplQueue类摘要如下: SplQueue简单使用如下: 复制代码 代码如下: $queue = new SplQueue();   /**  * 可见队列和双链表的区别就是IteratorMode改变了而已,栈的IteratorMode只能为:  * (1)SplDoublyL

  • Java PriorityQueue数据结构接口原理及用法

    PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列.优先级队列是不同于先进先出队列的另一种队列.每次从队列中取出的是具有最高优先权的元素.如果不提供Comparator的话,优先队列中元素默认按自然顺序排列,也就是数字默认是小的在队列头,字符串则按字典序排列(参阅 Comparable),也可以根据 Comparator 来指定,这取决于使用哪种构造方法.优先级队列不允许 null 元素.依靠自然排序的优先级队列还不允许插入不可比较的对象(

  • Java设计模式之装饰模式原理与用法实例详解

    本文实例讲述了Java设计模式之装饰模式原理与用法.分享给大家供大家参考,具体如下: 装饰模式能在不必改变原类文件和使用继承的情况下,动态地扩展一个对象的功能.它是通过创建一个包装对象,也就是装饰来包裹真实的对象.JDK中IO的设计就用到了装饰模式,通过过滤流对节点流进行包装来实现功能的扩展. 装饰模式的角色的组成: ① 抽象构件(Component)角色:给出一个抽象接口,以规范准备接收附加工功能的对象.(InputStream.OutputStream) ② 具体构件(Concrete Co

  • Java基础之代理原理与用法详解

    本文实例讲述了Java基础之代理原理与用法.分享给大家供大家参考,具体如下: 1.什么是代理 动态代理技术是整个java技术中最重要的一个技术,它是学习java框架的基础,不会动态代理技术,那么在学习Spring这些框架时是学不明白的. 动态代理技术就是用来产生一个对象的代理对象的.在开发中为什么需要为一个对象产生代理对象呢? 举一个现实生活中的例子:歌星或者明星都有一个自己的经纪人,这个经纪人就是他们的代理人,当我们需要找明星表演时,不能直接找到该明星,只能是找明星的代理人.比如刘德华在现实生

  • Java设计模式之观察者模式原理与用法详解

    本文实例讲述了Java设计模式之观察者模式原理与用法.分享给大家供大家参考,具体如下: 什么是观察者模式 可以这么理解: 观察者模式定义了一种一对多的依赖关系,让多个观察者对象同时监听某一个主题对象. 这个主题对象在状态上发生变化时,会通知所有观察者对象,让它们能够自动更新自己. 也可以这样理解: 观察者模式是关于多个对象想知道一个对象中数据变化情况的一种成熟模式.观察者模式中有一个称作"主题"的对象和若干个称作"观察者"的对象,"主题"和&qu

  • Java字节缓冲流原理与用法详解

    本文实例讲述了Java字节缓冲流原理与用法.分享给大家供大家参考,具体如下: 一 介绍 BufferInputStresm和BufferOutputStream 这两个流类为IO提供了带缓冲区的操作,一般打开文件进行写入或读取操作时,都会加上缓冲,这种流模式提高了IO的性能. 二 各类中方法比较 从应用程序中把输入放入文件,相当于将一缸水倒入另外一个缸中: FileOutputStream的write方法:相当于一滴一滴地把水"转移过去. DataOutputStream的writeXXX方法:

  • java抽象类和接口定义与用法详解

    本文实例讲述了java抽象类和接口定义与用法.分享给大家供大家参考,具体如下: 抽象类 抽象类定义 只约定类所具有的抽象行为,没有具体实现相应行为. 语法格式 abstract class 类名{ 常量; 变量; 构造(); 访问修饰符abstract 返回类型 方法名;//抽象方法 普通方法; 静态方法(); } 应用场景 1.不适合创建对象. 2.有些功能没有必要实现,有不同的子类实现. 3.每次使用的都是子类的对象. 4.为所有的子类提供了一个模板,所有的子类都是在此模板的基础之上添加和修

  • java类和对象原理与用法分析

    本文实例讲述了java类和对象原理与用法.分享给大家供大家参考,具体如下: 面向对象编程OOP 类:相似对象的集合. 对象 对象:实体.一切可以被描述的事物. 属性:特征. 方法:动作,行为. 类和对象的区别 [1]类时抽象的,对象是具体的. [2]类是一个模板,创建出来的对象具备共同的属性和方法. [3]类是一种数据烈性.引用数据类型. 语法 public classs 类名{ //定义属性部分 属性1的类型 属性1: 属性2的类型 属性2: ... 属性3的类型 属性n; //定义方法部分

  • JavaScript 接口原理与用法实例详解

    本文实例讲述了JavaScript 接口原理与用法.分享给大家供大家参考,具体如下: js接口 意义: 提供一种以说明一个对象应该有哪些方法的手段. 接口是面向对象javascript程序员的工具箱中最有用的工具之一 接口的利弊: 对于一些中小型程序来说 使用接口很显然是不明智的,对项目来说接口的好处也不明显,只是徒增其复杂度而已. 对于接口的好处,那么显而易见 首先促进代码的重用,对于开发来讲,还可以告诉程序员那些类都使用了什么方法,如果你事先知道接口那么就减少了你在编码的时候对类与类之间冲突

  • Java中的接口和抽象类用法实例详解

    本文实例讲述了Java中的接口和抽象类用法.分享给大家供大家参考,具体如下: 在面向对象的概念中,我们知道所有的对象都是通过类来描绘的,但是并不是所有的类都是用来描绘对象的,如果一个类中没有包含足够的信息来描绘一个具体的对象,这样的类就是抽象类. 抽象类往往用来表征我们在对问题领域进行分析. 设计中得出的抽象概念,是对一系列看上去不同,但是本质上相同的具体概念的抽象,我们不能把它们实例化(拿不出一个具体的东西)所以称之为抽象. 比如:我们要描述"水果",它就是一个抽象,它有质量.体积等

  • Java图形界面Swing原理及用法解析

    这篇文章主要介绍了Java图形界面Swing原理及用法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 JButton组件 布局管理器 FlowLayout 流式布局 BorderLayout 方位布局 GridLayout 表格布局 绝对布局 JLable 组件 文本框组件 JPanel轻量级容器 创建事件监听类 (更换监听类实现监听) 窗口监听适配器 都可使用匿名类实现监听 每个监听方法都可以返回一个Event对象来返回监听值 以上就是本

随机推荐