文档章节

优先级队列(PriprityQueue)是一种什么样的数据结构

pumpkinHua
 pumpkinHua
发布于 2015/10/19 10:14
字数 1076
阅读 193
收藏 3
点赞 0
评论 0

优先级队列(PriprityQueue)是一种无界队列,基于优先级堆,它的元素根据自然顺序或者通过实现Comparator接口的自定义排序方式进行排序。这篇文章,我们将创建一个Items的优先级队列,基于价格排序,优先级队列用来实现迪科斯彻算法(Dijkstra algorithm)非常实用。值得注意的是他的迭代器并不保证有序,如果需要按顺序遍历,最好使用Arrays.sort(pd.toArray())方法。同时它的实现不是同步的,意味着在多线程中不是线程安全的对象,可以取而代之的是PriorityBlockingQueue,它能用于多线程环境。优先级队列提供了O(log(n))时间在出队和入队的方法上,比如:offer(),poll(),add(),但是对于检索操作如:peek(),element()提供的是常量(固定)时间。

如何使用PriorityQueue

这里是如何使用PriorityQueue的一个例子,如上所说,你可以使用特定的顺序来组织元素,可以是自然顺序或者元素实现Comparator接口,这个例子中,我们把Items对象放入优先级队列中,按照价格排序,你可以注意下Item类的compareTo方法,它与equals方法是保持一致的,这里把Item类作为内部静态类,把item存储在优先级队列中,你可以一直使用poll()方法获取价格最低的那个item。

package test;
 
import java.util.PriorityQueue;
import java.util.Queue;
 
/**
  * Java Program to show How to use PriorityQueue in Java. This example also demonstrate
  * that PriorityQueue doesn't allow null elements and how PriorityQueue keeps elements i.e. ordering.
  *
  * @author
 */
public class PriorityQueueTest {
 
    public static void main(String args[]) {
 
        Queue<Item> items = new PriorityQueue<Item>();
        items.add(new Item("IPone", 900));
        items.add(new Item("IPad", 1200));
        items.add(new Item("Xbox", 300));
        items.add(new Item("Watch", 200));
 
        System.out.println("Order of items in PriorityQueue");
        System.out.println(items);
 
        System.out.println("Element consumed from head of the PriorityQueue : " + items.poll());
        System.out.println(items);
 
        System.out.println("Element consumed from head of the PriorityQueue : " + items.poll());
        System.out.println(items);
 
        System.out.println("Element consumed from head of the PriorityQueue : " + items.poll());
        System.out.println(items);
 
        //items.add(null); // null elements not allowed in PriorityQueue - NullPointerException
 
    }
 
    private static class Item implements Comparable<Item> {
 
        private String name;
        private int price;
 
        public Item(String name, int price) {
            this.name = name;
            this.price = price;
        }
 
        public String getName() {
            return name;
        }
 
        public int getPrice() {
            return price;
        }
 
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Item other = (Item) obj;
            if ((this.name == null) ? (other.name != null) : !this.name.equals(other.name)) {
                return false;
            }
            if (this.price != other.price) {
                return false;
            }
            return true;
        }
 
        @Override
        public int hashCode() {
            int hash = 5;
            hash = 97  hash + (this.name != null ? this.name.hashCode() : 0);
            hash = 97  hash + this.price;
            return hash;
        }
 
        @Override
        public int compareTo(Item i) {
            if (this.price == i.price) {
                return this.name.compareTo(i.name);
            }
 
            return this.price - i.price;
        }
 
        @Override
        public String toString() {
            return String.format("%s: $%d", name, price);
        }      
 
    }
}

Output:

Order of items in PriorityQueue
 
[Watch: $200, Xbox: $300, IPone: $900, IPad: $1200]
Element consumed from head of the PriorityQueue : Watch: $200
 
[Xbox: $300, IPad: $1200, IPone: $900]
Element consumed from head of the PriorityQueue : Xbox: $300
 
[IPone: $900, IPad: $1200]
Element consumed from head of the PriorityQueue : IPone: $900
 
[IPad: $1200]


从上面的输出结果可以很清晰的看到优先级对象始终把最小的值保存在头部,它的排序规则取决于compareTo()方法,尽管它不一定所有元素都是按序排列的,但是它能保证队列的头一定是最小的元素,这也是TreeSet和PriorityQueue的区别,前者能保证所有元素按序排列,而优先级队列仅仅保证列的头是有序的,另一个需要注意的地方是PriorityQueue并不允许null元素存在,如果尝试添加null值,那么就会抛出NullPointException异常:

Exception in thread "main" java.lang.NullPointerException
        at java.util.PriorityQueue.offer(PriorityQueue.java:265)
        at java.util.PriorityQueue.add(PriorityQueue.java:251)
        at test.PriorityQueueTest.main(PriorityQueueTest.java:36)
Java Result: 1

总结:

  1. 优先级队列不是同步的,如果需要保证线程安全那么请使用PriorityBlockingQueue

  2. 队列的获取操作如poll(),peek()和element()是访问的队列的头,保证获取的是最小的元素(根据指定的排序规则)

  3. 返回的迭代器并不保证提供任何的有序性

  4. 优先级队列不允许null元素,否则抛出NullPointException。

以上所有就是有关优先级队列的全部,它是一个很特别的类,用在一些特性的情景。记住:BlockingQueue维持的是插入的顺序,如果想维持自定义的顺序PriorityQueue或者PriorityBlockingQueue是正确的选择,TreeSet提供类似的功能,但是没有类似的检索+移除的方法:poll()

原文链接: Javarevisited 翻译: ImportNew.com 刘志军
译文链接: http://www.importnew.com/6510.html
转载请保留原文出处、译者和译文链接。]

本文转载自:http://www.importnew.com/6510.html

共有 人打赏支持
pumpkinHua
粉丝 3
博文 16
码字总数 3338
作品 0
衡阳
程序员
Java数据结构与算法(第四章栈和队列)

本章涉及的三种数据存储类型:栈、队列和优先级队列。 不同类型的结构 程序员的工具 数组是已经介绍过的数据存储结构,和其他结构(链表、树等等)一样,都适用于数据应用中作数据记录。 然而...

小风89 ⋅ 2015/10/24 ⋅ 0

数据结构-05-队列(Queue)

Queue - 队列 Queue 是一个 FIFO(先进先出)的数据结构,并发中使用较多,可以安全地将对象从一个任务传给另一个任务。 Queue 和 Stack 在 Python 中都是有 list ,[] 实现的。 在python 中l...

Corwien ⋅ 2016/06/17 ⋅ 0

堆、优先级队列和堆排序

堆结构是一种数组对象,其定义如下:它是完全二叉树或者近似完全二叉树。经常作为优先级队列,比如二叉树优先级队列,四叉树优先级队列。 n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当...

长平狐 ⋅ 2013/12/25 ⋅ 0

进程与进程调度优先

这里先说一下进程: 进程(Process)是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,是操作系统结构的基础。在早期面向进程设计的计算机结构中,进程...

Sevenot_Hu ⋅ 2017/07/08 ⋅ 0

基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

1、认识 PriorityQueue PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具...

xrzs ⋅ 2013/06/02 ⋅ 0

数据结构与算法——常用数据结构

把数据结构与算法C++描述大致的翻了一遍,把里面大致提到的数据结构和算法的名词记录下来,逐一攻克。 Go and fight! 链表:链表由一系列不必在内存中相连的数据组成,每一个节点均包含表元素...

mettaworldpeace ⋅ 2014/03/03 ⋅ 0

数据结构和算法的选择

http://www.cnblogs.com/people/p/3291343.html 数据结构和算法的选择   本部分总结前面介绍的数据结构和算法,并讨论在不同的情况下如何进行选择。 通用数据结构:数组、链表、树、哈希表...

污湖洞主 ⋅ 2017/06/12 ⋅ 0

QOS队列类型简介(CQ、PQ、WFQ、CBWFQ)

对于网络单元,当分组到达的速度大于该接口传送分组的速度时,在该接口处就会产生拥塞。如果没有足够的存储空间来保存这些分组,它们其中的一部分就会丢失。分组的丢失又可能会导致发送该分组...

彦天天 ⋅ 2017/08/15 ⋅ 0

QOS队列类型简介(CQ、PQ、WFQ、CBWFQ)

对于网络单元,当分组到达的速度大于该接口传送分组的速度时,在该接口处就会产生拥塞。如果没有足够的存储空间来保存这些分组,它们其中的一部分就会丢失。分组的丢失又可能会导致发送该分组...

aloofcn ⋅ 2014/04/26 ⋅ 0

STL系列之五 priority_queue 优先级队列

priorityqueue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优...

彭博 ⋅ 2012/04/12 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

AppDelegate 设置Root相关

self.window = UIWindow.init(frame: UIScreen.main.bounds) self.window?.backgroundColor = UIColor.white self.window?.makeKeyAndVisible() self.window?.rootViewController = RootTabB......

west_zll ⋅ 4分钟前 ⋅ 0

Java并发系列5--倒计时器CountDownLatch

今天讲一个倒计时器工具,叫CountDownLatch。需要这个工具的场景大概有:当所有的小任务都完成之后,再启动大任务。 先看代码: public class CountDownLatchDemo {static final CountDow...

大大枣 ⋅ 5分钟前 ⋅ 0

SpreadJS使用进阶指南 - 使用 NPM 管理你的项目

前言 SpreadJS作为一款性能出众的纯前端电子表格控件,自2015年发布以来,已经被广泛应用于各领域“在线Excel”数据管理项目中。NPM,作为管理Node.js库最有力的手段,解决了很多NodeJS代码部...

葡萄城控件技术团队 ⋅ 6分钟前 ⋅ 0

Mac下IntelliJ IDEA快捷键大全

https://blog.csdn.net/lisongjia123/article/details/54949364

细节探索者 ⋅ 9分钟前 ⋅ 0

建造者模式

1、工厂模式中创建的对象大都是简单的对象 复杂的产品类并且拥有不同的属性特点的管理就需要用到建造者模式 2、建造者模式: 将一个复杂的对象的构建与它的表示分离,使得同样的构建过程可以...

职业搬砖20年 ⋅ 10分钟前 ⋅ 0

Mysql数据库开发 怎么优化SQL语句?

 1) 现场抓出慢查询语句 show full processlist;   2) 配置参数:   slow_query_log_file = ON 慢查询开启开关   long_query_time =2 记录大于2秒的sql语句   log_queries_not_usi...

老男孩Linux培训 ⋅ 11分钟前 ⋅ 0

Laravel 安装执行php artisan migrate 出现字段过长错误

最近在自己研究Laravel Laravel版本:5.6 PHP版本:7.1.9 Mysql版本:5.7.19 Apache版本:2.4.27 系统版本:windows10 首先要保证电脑安装了composer,和node.js 执行命令 composer global ...

Marhal ⋅ 16分钟前 ⋅ 0

ELK6.0日志从收集到处理完整版教程(二)

ELK简介 Elasticsearch 开源分布式搜索引擎,它的特点有:分布式,零配置,自动发现,索引自动分片,索引副本机制,restful风格接口,多数据源,自动搜索负载等。也可以认为ElasticSearch是一...

bz_z ⋅ 19分钟前 ⋅ 0

Spark项目之电商用户行为分析大数据平台之(七)数据调研--基本数据结构介绍

目录 一、user_visit_action(Hive表) 1.1 表的结构 1.2 表的说明 二、user_info(Hive表) 2.1 表的结构 2.2 表的说明 三、task(MySQL表) 3.1 表的结构 3.2 表的说明 四、工作流程...

xiaomin0322 ⋅ 24分钟前 ⋅ 0

评分卡模型剖析之一(woe、IV、ROC、信息熵)

信用评分卡模型在国外是一种成熟的预测方法,尤其在信用风险评估以及金融风险控制领域更是得到了比较广泛的使用,其原理是将模型变量WOE编码方式离散化之后运用logistic回归模型进行的一种二...

火力全開 ⋅ 24分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部