文档章节

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

pumpkinHua
 pumpkinHua
发布于 2015/10/19 10:14
字数 1076
阅读 200
收藏 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
242
0
JavaScript 事件循环机制

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

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

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

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

没有更多内容

加载失败,请刷新页面

加载更多

eslint rules 规则

'rules': { "comma-dangle": ["error", "never"], //是否允许对象中出现结尾逗号 "no-cond-assign": 2, //条件语句的条件中不允许出现赋值运算符 "no-console": 2, //不允许出现console语句 ...

agenyun
22分钟前
1
0
类型判断时instanceof和equals的不同用法

接口设计时为了避免序列化的麻烦,将接口定义为参数为map<String,String>类型的接口,但是现在调用时需要转换当前的实体Bean为Map,接口接收方再把Map转换为另一个Bean实体。过程中的需要对类...

wangtx
28分钟前
1
0
vue 组件间传值(个人精编)

1.父组件向子组件传值 1⃣️.子组件标签绑定需要传递的参数名2⃣️.子组件页面使用props 接收参数 2.子组件向父组件传值  1⃣️.子组件使用$emit来触发一个自定义事件,并传递一个参...

MrBoyce
39分钟前
1
0
(荷兰)彼得·冯·门施著:博物馆学研究的目的

博物馆学研究的目的 (荷)彼得·冯·门施 尽管诸多关于博物馆学认知目的的不同看法可以被归纳为数个主要群体,但没有一个群体可以被称为“学派”。一般来说,学派是由于博物馆学研究目的的不...

乔老哥
48分钟前
2
0
Vue slot的用法

之前看官方文档,由于自己理解的偏差,不知道slot是干嘛的,看到小标题,使用Slot分发内容,就以为 是要往下派发内容。然后就没有理解插槽的概念。其实说白了,使用slot就是先圈一块地,将来...

peakedness丶
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部