Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 678|回复: 0

[算法学习]堆实现的优先队列(JAVA)

[复制链接]
  • TA的每日心情
    开心
    2021-3-12 23:18
  • 签到天数: 2 天

    [LV.1]初来乍到

    发表于 2014-12-4 00:07:59 | 显示全部楼层 |阅读模式
    优先队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。

    优先队列主要方法:
    void add(Object o);//进队
    void offer(Object o);//进队
    Object poll();//出队
    Object peek();//查看队列首元素
    boolean isEmpty();
    int size();

         在下面例子中用基于数组的堆实现优先队列,即堆中的元素保存在一个数组中。

         堆是一种二叉树,所遵守的唯一规律为:所有的子节点都要大于(小于)父节点。而这个数组元素的保存也是按照一定规律的:如果父结点的位置为n,那么,其对应的左右子结点的位置分别是2n+1和2n+2。   
      
       
       

         
       

         
       
      



          
    堆有两个很基本的操作:
    增加一个节点,直接加在最后,然后用重新调整堆.

    删除一个节点,则把要删除的节点与最后一个节点交换,然后删除交换后的节点(既最后一个节点),然后重新调整堆.
    假如有下面这样一个堆:


    这时候,有一个元素1要添加进来,这时候应该怎么办呢?第一步,将元素添加到堆的最后一个位置:

      
      第二步,将新加入的元素与其父结点的值进行比较,若新结点的值比其父结点的值要小(就像这个例子一样),那么,交换两个结点的值,重复第二步,直到形成一个小顶堆:


    这样,一个新的小顶堆诞生了!
    然后就是从堆中删除一个元素了,假设在这个新的小顶堆中,我们打算删除堆顶元素:
    第一步,将这个1删掉,假设其结点上当前没有值:


    第二步,将最后一个结点的值放在根的位置,然后进行下滤,比较一下两个子结点的值与根节点的值,将堆顶元素与其子结点中较小的交换,然后重复:


    知道了这些基本的原理,对数据量更大的增加和删除也应该是触类旁通了吧。
    有人会质疑堆中除堆顶元素之外的其他元素的顺序问题:


    比如这里为什么4会放在5的右边兄弟结点上,这明显是受了二叉查找树的影响,因为堆对我们来说,一般只有堆顶元素有用,因此只要保证堆顶元素是最小的就行了(对小顶堆)。

      
    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
            }
    }
    [/code]



    测试:


    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);
       }
      };
    }
    }
    [/code]

    运行:



    D:ex>java  PQTest

    1

    2







      
      
       
       

         
       

         
       
      
    复制代码

    源码下载:http://file.javaxxz.com/2014/12/4/000759015.zip
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2025-2-25 04:18 , Processed in 0.364398 second(s), 46 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表