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

http://www.importnew.com/6510.html

优先级队列（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。

import java.util.PriorityQueue;
import java.util.Queue;

public class test2 {

	public static void main(String args[]) {
		 
        Queue items = new PriorityQueue();
        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 {
 
        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 = hash + (this.name != null ? this.name.hashCode() : 0);
            hash = 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);
        }      
 
    }
}

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]

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()