堆实现的优先队列（JAVA）

堆实现的优先队列（JAVA）
  优先队列，顾名思义，就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体，不仅可以存储数据，还可以将这些数据按照我们设定的规则进行排序。

class  PriorityQueue {
        protected Comparator comparator;
        final static int ROOT_INDEX = 0;
        final static int PRE_ROOT_INDEX = ROOT_INDEX - 1;
        List heap;//存放队列元素的堆
        public PriorityQueue() {
                heap = new ArrayList();
        }
        public PriorityQueue(Comparator c) {
                heap = new ArrayList();
                comparator = c;
        }
       
        public void add(Object o) {
                heap.add(o);//在最后增加一个元素
                int index = heap.size() - 1;//最后一个元素的索引
                while (index > ROOT_INDEX) {//在堆中加一个元素后,调整堆使其再成为一个堆
                        index = stepUpHeap(index);//上浮
                }
        }
        public void offer(Object o){
              add(o);
        }
        protected int stepUpHeap(int index) {
          int parentIndex = parent(index);//获取父节点的索引
          Object element = heap.get(index);
          Object parent  = heap.get(parentIndex);
          if (compare(parent, element) > 0) { //父节点大于儿子节点,交换
                heap.set(parentIndex, element);
                heap.set(index, parent);
                return parentIndex;  // 跳到父索引
           } else   
                return ROOT_INDEX; //不需要交换
        }
       //比较器
        protected int compare(Object element, Object other) {
           if (comparator == null) {
                 Comparable e = (Comparable) element;
                 Comparable o = (Comparable) other;
                 return e.compareTo(o);
            } else
                  return comparator.compare(element, other);
        }
        
        protected int parent(int index) {
          return (index - PRE_ROOT_INDEX) / 2 + PRE_ROOT_INDEX;
        }
        public String toString() {
                return heap.toString();
        }
       
        public boolean isEmpty() {
                return heap.isEmpty();
        }
      
        public int size() {
                return heap.size();
        }
         
        public Object peek() throws RuntimeException{
          if (isEmpty())
               throw new RuntimeException();
           return heap.get(0);
         }
      
        public Object poll() throws RuntimeException{//取优先队列头元素
            if (isEmpty())
               throw new RuntimeException();
            int index = heap.size() - 1;//最后一个元素的索引
            Object least;
            if(index==0){
               least = heap.get(index);
               heap.remove(index);
            }
            else{
               Object element = heap.get(index);//取最后一个元素
               least  = heap.get(ROOT_INDEX);//取堆的根元素
               heap.set(ROOT_INDEX, element);//交换这两个元素
               heap.set(index, least);
               heap.remove(index);//删除最后一个元素
               stepDownHeap(ROOT_INDEX);//下沉调整,使之再次成为堆
            }
                return least;
        }
                   
        public void stepDownHeap(int index){
                int p = index;
                int c = 2*p + 1;//左子节点
                Object temp = heap.get(p);//
                while(c<heap.size()){
         if(c+1<heap.size() && compare(heap.get(c+1),heap.get(c))<0)//右节点比左节点小
                                c = c + 1;//取两个儿子节点中小的一个
                        if(compare(temp,heap.get(c))<=0)//不需要调整了
                                break;
                        else {
                             heap.set(p,heap.get(c));//较小的儿子节点上浮
                                p = c;
                                c = 2*p + 1;//继续调整
                       }
                }
                heap.set(p,temp);//最后要将temp放到p
        }
}

Read full article from 堆实现的优先队列（JAVA）