用堆实现简单的优先队列（JAVA）
优先队列，顾名思义，就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体，不仅可以存储数据，还可以将这些数据按照我们设定的规则进行排序。
优先队列主要方法:
void add(Object o);//进队
void offer(Object o);//进队
Object poll();//出队
Object peek();//查看队列首元素
boolean isEmpty();
int size();

在下面例子中用基于数组的堆实现优先队列，即堆中的元素保存在一个数组中。堆是一种二叉树，所遵守的唯一规律为：所有的子节点都要大于（小于）父节点。而这个数组元素的保存也是按照一定规律的：如果父结点的位置为n，那么，其对应的左右子结点的位置分别是2n+1和2n+2。

堆有两个很基本的操作：
增加一个节点，直接加在最后，然后用重新调整堆(参看http://128kj.iteye.com/blog/1728555)

删除一个节点，则把要删除的节点与最后节点交换，然后删除交换后的节点（既最后一个点），然后重新调整堆.

import java.util.Comparator;public class PQTest {   public static void main(String[] args) { Comparator c=comparableComparator();   PriorityQueue pq=new PriorityQueue(c);   pq.add(2);   pq.add(101);   pq.add(1);   System.out.println(pq.poll());   System.out.println(pq.peek()); } static Comparator comparableComparator() {  return new Comparator() {   public int compare(Object x, Object y) {    return ((Comparable) x).compareTo(y);   }  }; }}

运行:

D:\ex>java PQTest
1
2
下载源码