当前位置:首页 > 开发 > 编程语言 > Java > 正文

用堆实现简单的优先队列(JAVA)

发表于: 2012-11-18   作者:128kj   来源:转载   浏览:
摘要:    优先队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。 优先队列主要方法: void add(Object o);//进队 void offer(Object o);//进队 Object poll();//出队 Object peek();//查看
   优先队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。
优先队列主要方法:
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)

删除一个节点,则把要删除的节点与最后节点交换,然后删除交换后的节点(既最后一个点),然后重新调整堆.

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
        }
}




测试:
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
下载源码

用堆实现简单的优先队列(JAVA)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一般数据结构中的堆指的是二叉堆(Binary heap)。堆是一棵完全二叉树,可用数组来表示。对于数组中任
前言 数据结构队列的学习中,我们知道队列是先进先出的。任务被提交到队列中,按照先进先出的原则
本文将先简单的介绍一下二叉堆,然后再使用二叉堆实现优先队列。 1、二叉堆实际上就是一种完全二叉
零路径长度(null path length, NPL),NPL(X)定义为从X到一个没有两个儿子的节点的最短路径的长。因
什么是堆: 堆的定义:n个元素的序列k={k0,k1,……,kn-1},当且仅满足条件 (1)ki >= k2i+1 和 ki
队列的特点是先进先出。通常都把队列比喻成排队买东西,大家都很守秩序,先排队的人就先买东西。 但
上一节我们写了树以及二叉树的知识 http://blog.csdn.net/wtyvhreal/article/details/43487095 堆是
优先队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结
1.优先队列有两项基本操作:插入(insert)和删除最小项(deleteMin),后者的工作是找出、返回和删
接着上一Pa说。就是如何建立这个堆呢。可以从空的堆开始,然后依次往堆中插入每一个元素,直到所有
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号