文档章节

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

pumpkinHua
 pumpkinHua
发布于 2015/10/19 10:14
字数 1076
阅读 193
收藏 3

优先级队列(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
250
0
数据结构-05-队列(Queue)

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

Corwien
2016/06/17
17
0
堆、优先级队列和堆排序

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

长平狐
2013/12/25
170
0
JavaScript 事件循环机制

前端开发的童鞋应该都知道,JavaScript 是一门单线程的脚本语言。这就意味着 JavaScript 代码在执行的时候,只有一个主线程来执行所有的任务,同一个时间只能做同一件事情。 那么为什么 Java...

淘淘笙悦
07/09
0
0
基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

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

大数据之路
2013/06/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Memcached启动参数详解

memcached -d -m 1024 -l 192.168.100.101 -p 11211 -P /tmp/memcached.pid -c 1024 -f 1.25 -n 80 -t 16 运行参数描述 -d:以守护(daemon)进程方式启动; -u:是运行Memcache的用户,例如 ......

月下狼
19分钟前
0
0
xgboost-kaggle

https://www.kaggle.com/dansbecker/xgboost This tutorial is part of the Learn Machine Learning series. In this step, you will learn how to build and optimize models with the powe......

tantexian
19分钟前
0
0
nginx学习八 代理服务

最常用的语法 proxy_pass Syntax: proxy_pass URL;Default: --Context:location.if in location,limit_exception 反向代理 例:/etc/nginx/conf.d/default.conf 反向代理(代理服务端)......

Romanceling
27分钟前
0
0
npm ERR! Unexpected end of JSON ...

npm install 报错: npm ERR! Unexpected end of JSON input while parsing near '..."^2.8.14"},"_hasShrin' npm ERR! A complete log of this run can be found in: ... 打开终端 命令: 第......

大_侠
31分钟前
0
0
Android中的设计模式之责任链模式

参考 《设计模式:可复用面向对象软件的基础 》5.1 Chain of responsibility 职责链 对象行为型模式 《Android源码设计模式解析与实战》第9章 使编程更有灵活性--责任链模式 意图 使多个对象...

newtrek
34分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部