文档章节

优先级队列(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
Priority_Queue(优先队列)

我们都知道,队列是一种FIFO的数据结构,规定在队尾增加元素,在队首删除元素,和食堂排队打饭一个道理。(当然,插队的人是很鄙视的)。而在优先队列中,每个元素却有了特权,被赋予了优先级...

回忆酿的甜
01/22
0
0
堆、优先级队列和堆排序

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

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

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

淘淘笙悦
2018/07/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java中的ReentrantLock和synchronized两种锁定机制的对比

多线程和并发性并不是什么新内容,但是 Java 语言设计中的创新之一就是,它是第一个直接把跨平台线程模型和正规的内存模型集成到语言中的主流语言。核心类库包含一个 Thread 类,可以用它来构...

watermelon11
7分钟前
0
0
Tomcat的日志

Tomcat的日志 Tomcat日志在/usr/local/tomcat/logs目录下,大概有一下几类文件: catalina.outcatalina.xxx-xx-xx.loghost-manager.xxxx-xx-xx.logmanager.xxxx-xx-xx.loglocalhost.xxx......

wzb88
28分钟前
1
0
PHP7源码编译安装详解

下面进行编译安装PHP7.0,编译安装最头疼的就是因为某些类库没有安装而报错,所以编译前请确保以下包已安装。 $ yum groupinstall "development tools"$ yum install -y gcc gcc-c++ aut...

Linux就该这么学
46分钟前
3
0
Java引用传递和JVM堆栈的关系说明

通过代码说明 Java 引用传递在堆栈上的关系。 可以从JVM的内存空间存放上说明,值传递 和引用传递。 堆(线程共享):对象、对象的全局变量、数组 栈(线程私有):声明为局部变量的 基本数据...

冷基
今天
2
0
直接插入排序

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。直接插入排序的时间复杂度为O(n^2),但性能比冒泡排序和简单选择排序的性能要好一点...

niithub
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部