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

这篇文章主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

一、优先队列概述

优先队列PriorityQueue是Queue接口的实现，可以对其中元素进行排序，

可以放基本数据类型的包装类（如：Integer，Long等）或自定义的类

对于基本数据类型的包装器类，优先队列中元素默认排列顺序是升序排列

但对于自己定义的类来说，需要自己定义比较器

二、常用方法

  • peek()//返回队首元素
  • poll()//返回队首元素，队首元素出队列
  • add()//添加元素
  • size()//返回队列元素个数
  • isEmpty()//判断队列是否为空，为空返回true,不空返回false

三、优先队列的使用

1.队列保存的是基本数据类型的包装类

//自定义比较器，降序排列
static Comparator<Integer> cmp = new Comparator<Integer>() {
  public int compare(Integer e1, Integer e2) {
  return e2 - e1;
  }
 };
public static void main(String[] args) {
  //不用比较器，默认升序排列
  Queue<Integer> q = new PriorityQueue<>();
  q.add(3);
  q.add(2);
  q.add(4);
  while(!q.isEmpty())
  {
   System.out.print(q.poll()+" ");
  }
  /**
   * 输出结果
   * 2 3 4
   */
  //使用自定义比较器，降序排列
  Queue<Integer> qq = new PriorityQueue<>(cmp);
  qq.add(3);
  qq.add(2);
  qq.add(4);
  while(!qq.isEmpty())
  {
   System.out.print(qq.poll()+" ");
  }
  /**
   * 输出结果
   * 4 3 2
   */
}

2.队列保存的是自定义类

//矩形类
class Node{
 public Node(int chang,int kuan)
 {
  this.chang=chang;
  this.kuan=kuan;
 }
 int chang;
 int kuan;
}

public class Test {
　　　　//自定义比较类，先比较长，长升序排列，若长相等再比较宽，宽降序
 static Comparator<Node> cNode=new Comparator<Node>() {
  public int compare(Node o1, Node o2) {
   if(o1.chang!=o2.chang)
    return o1.chang-o2.chang;
   else
    return o2.kuan-o1.kuan;
  }

 };
 public static void main(String[] args) {
  Queue<Node> q=new PriorityQueue<>(cNode);
  Node n1=new Node(1, 2);
  Node n2=new Node(2, 5);
  Node n3=new Node(2, 3);
  Node n4=new Node(1, 2);
  q.add(n1);
  q.add(n2);
  q.add(n3);
  Node n;
  while(!q.isEmpty())
  {
   n=q.poll();
   System.out.println("长: "+n.chang+" 宽：" +n.kuan);
  }
　　　　　/**
　　　　　　* 输出结果
　　　　　　* 长: 1 宽：2
　　　　　　* 长: 2 宽：5
　　　　　　* 长: 2 宽：3
　　　　　　*/
 }
}

3.优先队列遍历

　　PriorityQueue的iterator（）不保证以任何特定顺序遍历队列元素。

　　若想按特定顺序遍历，先将队列转成数组，然后排序遍历

示例

Queue<Integer> q = new PriorityQueue<>(cmp);
  int[] nums= {2,5,3,4,1,6};
  for(int i:nums)
  {
   q.add(i);
  }
  Object[] nn=q.toArray();
  Arrays.sort(nn);
  for(int i=nn.length-1;i>=0;i--)
   System.out.print((int)nn[i]+" ");
  /**
   * 输出结果
   * 6 5 4 3 2 1
   */

4.比较器生降序说明

Comparator<Object> cmp = new Comparator<Object>() {
  public int compare(Object o1, Object o2) {
   //升序
   return o1-o2;
   //降序
   return o2-o1;
  }
 };

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

赞 (0)

相关推荐

  • Java数组模拟优先级队列数据结构的实例

    优先级队列 如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列 这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先

  • 详细分析Java并发集合LinkedBlockingQueue的用法

    在上一章我们讲解了ArrayBlockingQueue,用数组形式实现的阻塞队列. 数组的长度在创建时就必须确定,如果数组长度小了,那么ArrayBlockingQueue队列很容易就被阻塞,如果数组长度大了,就容易浪费内存. 而队列这个数据结构天然适合用链表这个形式,而LinkedBlockingQueue就是使用链表方式实现的阻塞队列. 一. 链表实现 1.1 Node内部类 /** * 链表的节点,同时也是通过它来实现一个单向链表 */ static class Node<E> { E

  • 详细分析Java并发集合ArrayBlockingQueue的用法

    在上一章中,我们介绍了阻塞队列BlockingQueue,下面我们介绍它的常用实现类ArrayBlockingQueue. 一. 用数组来实现队列 因为队列这种数据结构的特殊要求,所以它天然适合用链表的方式来实现,用两个变量分别记录链表头和链表尾,当删除或插入队列时,只要改变链表头或链表尾就可以了,而且链表使用引用的方式链接的,所以它的容量几乎是无限的. 那么怎么使用数组来实现队列,我们需要四个变量:Object[] array来存储队列中元素,headIndex和tailIndex分别记录队列

  • Java并发之BlockingQueue的使用

    本文主要讲的是并发包中涉及到的集合,关于普通集合,请参考[java 集合概览] 一.什么是BlockingQueue BlockingQueue即阻塞队列,从阻塞这个词可以看出,在某些情况下对阻塞队列的访问可能会造成阻塞.被阻塞的情况主要有如下两种: 1. 当队列满了的时候进行入队列操作 2. 当队列空了的时候进行出队列操作 因此,当一个线程试图对一个已经满了的队列进行入队列操作时,它将会被阻塞,除非有另一个线程做了出队列操作:同样,当一个线程试图对一个空队列进行出队列操作时,它将会被阻塞,除非

  • java编程实现优先队列的二叉堆代码分享

    这里主要介绍的是优先队列的二叉堆Java实现,代码如下: package practice; import edu.princeton.cs.algs4.StdRandom; public class TestMain { public static void main(String[] args) { int[] a = new int[20]; for (int i = 0; i < a.length; i++) { int temp = (int)(StdRandom.random()*1

  • Java多线程Queue、BlockingQueue和使用BlockingQueue实现生产消费者模型方法解析

    Java多线程Queue、BlockingQueue和使用BlockingQueue实现生产消费者模型方法解析

    Queue是什么 队列,是一种数据结构.除了优先级队列和LIFO队列外,队列都是以FIFO(先进先出)的方式对各个元素进行排序的.无论使用哪种排序方式,队列的头都是调用remove()或poll()移除元素的.在FIFO队列中,所有新元素都插入队列的末尾. Queue中的方法 Queue中的方法不难理解,6个,每2对是一个也就是总共3对.看一下JDKAPI就知道了: 注意一点就好,Queue通常不允许插入Null,尽管某些实现(比如LinkedList)是允许的,但是也不建议. Blocking

  • Java基于堆结构实现优先队列功能示例

    Java基于堆结构实现优先队列功能示例

    本文实例讲述了Java基于堆结构实现优先队列功能.分享给大家供大家参考,具体如下: package Demo; import java.util.NoSuchElementException; /* * 小顶堆 java使用堆结构实现优先队列 */ public class JPriorityQueue<E> { @SuppressWarnings("hiding") class QueueNode<E> { int capacity; int size; E[

  • java并发学习之BlockingQueue实现生产者消费者详解

    java并发学习之BlockingQueue实现生产者消费者详解

    1.介绍 阻塞队列 (BlockingQueue)是Java util.concurrent包下重要的数据结构,BlockingQueue提供了线程安全的队列访问方式:当阻塞队列进行插入数据时,如果队列已满,线程将会阻塞等待直到队列非满:从阻塞队列取数据时,如果队列已空,线程将会阻塞等待直到队列非空.并发包下很多高级同步类的实现都是基于BlockingQueue实现的. JDK7提供了以下7个阻塞队列: ArrayBlockingQueue :由数组结构组成的有界阻塞队列. LinkedBloc

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

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

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

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

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

  • Java List 用法详解及实例分析

    Java List 用法详解及实例分析 Java中可变数组的原理就是不断的创建新的数组,将原数组加到新的数组中,下文对Java List用法做了详解. List:元素是有序的(怎么存的就怎么取出来,顺序不会乱),元素可以重复(角标1上有个3,角标2上也可以有个3)因为该集合体系有索引 ArrayList:底层的数据结构使用的是数组结构(数组长度是可变的百分之五十延长)(特点是查询很快,但增删较慢)线程不同步 LinkedList:底层的数据结构是链表结构(特点是查询较慢,增删较快) Vector

  • java锁机制ReentrantLock源码实例分析

    java锁机制ReentrantLock源码实例分析

    目录 一:简述 二:ReentrantLock类图 三:流程简图 四:源码分析 lock()源码分析: 非公平实现: 公平锁实现: tryAcquire()方法 公平锁实现: 非公平锁实现: addWaiter() acquireQueued() shouldParkAfterFailedAcquire() parkAndCheckInterrupt() unlock()方法源码分析: tryRelease() unparkSuccessor() 五:总结 一:简述 ReentrantLock是

  • Java设计模式之静态代理模式实例分析

    本文实例讲述了Java设计模式之静态代理模式.分享给大家供大家参考,具体如下: 代理模式,可以通过代理可以在原来的基础上附加一些其他的操作.静态代理模式相对比较简单无需再程序运行时动态的进行代理. 静态代理模式的角色: ① 抽象角色:真实对象和代理对象的共同接口.其中声明真实对象和代理对象需要做的事. ② 真实角色:实现抽象角色,定义真实角色所要实现的业务逻辑,供代理角色调用. ③ 代理角色:实现抽象角色,是真实角色的代理,通过真实角色的业务逻辑方法来实现抽象方法,并可以附加自己的操作. 下面提

  • java阻塞队列实现原理及实例解析

    java阻塞队列实现原理及实例解析

    这篇文章主要介绍了java阻塞队列实现原理及实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 阻塞队列与普通队列的不同在于.当队列是空的时候,从队列中获取元素的操作将会被阻塞,或者当队列满时,往队列里面添加元素将会被阻塞.试图从空的阻塞队列中获取元素的线程将会被阻塞,直到其他的线程往空的队列插入新的元素.同样,试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞,直到其他的线程使队列重新变得空闲起来,如从队列中移除一个或者多个元素,或者完

  • Java内存模型原子性原理及实例解析

    这篇文章主要介绍了Java内存模型原子性原理及实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 本文就具体来讲讲JMM是如何保证共享变量访问的原子性的. 原子性问题 原子性是指:一个或多个操作,要么全部执行且在执行过程中不被任何因素打断,要么全部不执行. 下面就是一段会出现原子性问题的代码: public class AtomicProblem { private static Logger logger = LoggerFactory.

  • Java原子变量类原理及实例解析

    这篇文章主要介绍了Java原子变量类原理及实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.原子变量类简介 为何需要原子变量类 保证线程安全是 Java 并发编程必须要解决的重要问题.Java 从原子性.可见性.有序性这三大特性入手,确保多线程的数据一致性. 确保线程安全最常见的做法是利用锁机制(Lock.sychronized)来对共享数据做互斥同步,这样在同一个时刻,只有一个线程可以执行某个方法或者某个代码块,那么操作必然是原子性

  • java中ThreadLocal的应用场景实例分析

    说到线程的安全,我们可以通过ThreadLocal来解决.但作为一种强大的变量,它的应用场景远不止如此.在各类的框架中,我们依然可以使用来对它们进行管理.同时在使用ThreadLocal时需要注意内存泄漏的问题.下面我们就这两点进行分析,并带来对应代码的展示. 1.各种框架中的应用 Spring框架的事务管理中使用ThreadLocal来管理连接,每个线程是单独的连接,当事务失败时不能影响到其他线程的事务过程或结果,还有大家耳闻目睹的ORM框架.Mybatis也是用ThreadLocal管理,S

  • Java用POI导入导出Excel实例分析

    1.异常java.lang.NoClassDefFoundError: org/apache/poi/UnsupportedFileFormatException 解决方法: 使用的poi的相关jar包一定版本一定要相同!!!!! 2.maven所使用jar包,没有使用maven的话,就用poi-3.9.jar和poi-ooxml-3.9.jar(这个主要是用于Excel2007以后的版本)两个jar包就行() <dependency> <groupId>org.apache.po

  • Java布隆过滤器的原理和实现分析

    目录 前言 1. 预备知识 1.1 哈希函数 2. 布隆过滤器 2.1 概念 2.2 实现原理 2.3 步骤 2.4 实现 前言 数组.链表.树等数据结构会存储元素的内容,一旦数据量过大,消耗的内存也会呈现线性增长 所以布隆过滤器是为了解决数据量大的一种数据结构 讲述布隆过滤器的时候需要了解一些预备的知识点:比如哈希函数 1. 预备知识 1.1 哈希函数 哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数 一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定

随机推荐