硬核!手写一个优先队列-阿里云开发者社区

开发者社区> bigsai> 正文

硬核!手写一个优先队列

简介: 优先队列的原理是借助堆,通过本文图解让你更细致了解优先队列。
+关注继续查看

文章收录在首发公众号:bigsai 期待你的到访!

前言

事情还要从一个故事讲起:
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

对于上面那只可爱的小狗狗不会,本篇即为该教程,首先,我要告诉这只可爱的小狗狗,这种问题你要使用的数据结构为优先队列,每次操作的时间复杂度为O(logn),而整个过程的时间复杂度为O(nlogn).

对于本片的设计与实现和堆排序可能有些相似,因为他们都借助堆来实现算法和数据结构,下面详细介绍优先队列的设计与实现

而堆就是一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树(完全)的数组对象。且总是满足以下规则:

  • 堆总是一棵完全二叉树
  • 每个节点总是大于(或小于)它的孩子节点。

对于完全二叉树,我想大家都能明白,就是最底层叶子节点要严格按照从左向右来。
在这里插入图片描述
堆有大根堆和小根堆,如果是所有父节点都大于子节点的时候,那么这就是个大根堆,反之则为小根堆,以下就是一个大根堆:
在这里插入图片描述
最后需要注意的是我们并不是用链式去储存这个二叉树而是用数组去存储这个树,虽然链式的使用场景可能更多一些,但是在完全二叉树的情况下空间使用率较好没有斜树的出现。并且在操作的时候可以直接通过编号找到位置进行交换。

优先队列

如何理解优先队列,我们先从一段对话说起:
在这里插入图片描述

优先队列,它是一个队列。而普通的队列遵从先进先出的规则。而优先队列遵循一个排序的规则:每次抛出自定义排序最大(小)的,默认的情况是抛出最小的,本篇也就从最基本的原理进行分析。

并且它的用法队列还是一样的,,所以我们在设计这个类的时候api方面要与队列的api一致。
在这里插入图片描述

我们主要实现add、poll、和peek方法,并且会着重于算法的实现而不太着重一些细节的实现。

虽然优先队列和堆排序利用堆结构特性的流程有一些相似,但是两者其实还是有些操作上的区别的:

堆排序

  • 刚开始是一个杂乱无章的序列,所以需要将杂乱的序列(树)通过一个方法变成一个合法的堆。
  • 转成一个堆之后需要删除n次每次删除完都要重新调整这个堆。没有插入操作

优先队列

  • 队列(堆)刚开始的内容为空,每次增加一个元素时需要即使调整堆。每次删除也要及时调整堆,增加和删除每次都只是一个元素。

但是优先队列的具体操作流程是如何的呢?我们具体分析其插入和删除的流程

插入add流程(小根堆为例):

  • 正常处理完的优先队列内的数据满足一个堆的结构,所以就是插入在堆中。
  • 堆是一棵完全二叉树,所以在插入初始,插入到最后一个位置不影响其他结构。
  • 节点和父节点比较大小(父节点索引为其二分之一)。如果该节点比父节点更小,则交换数据,一直到不能交换为止,这个过程不用担心不合法,因为父节点更小的话更满足比孩子节点更小。

在这里插入图片描述

删除pop流程(小根堆为例):

  • pop删除操作取优先队列内最小的元素,而这个元素肯定就是堆顶元素了,取完之后,这个堆的其他部分还是满足堆的结构但是缺少堆顶。
  • 为了不影响整个结构,我们将末尾的那个元素移到堆顶,此时堆需要调整使其满足堆的性质条件。
  • 交换的这个节点和左右孩子进行比较,如果需要交换则交换,交换后再次考虑交换子节点是否需要交换,一直到不交换为止。最坏情况是交换到根节点,这个复杂度每次为O(logn).

在这里插入图片描述

代码实现

我想到这里,优先队列的内部流程思想你已经掌握了,但是懂优先队列原理和手写优先队列是两个概念,为了更深入的学习优先队列,在这里就带你手写一个简易型的优先队列。

在代码的具体实现方面,最主要的就是pop()和add()两个函数了。在pop()函数具体实现的时候,将最后一个元素移到堆头考虑和其他孩子节点交换的时候,用while进行操作的时候计算孩子下标的时候要确保不越界。我们用的是数组存储数据,优先队列的长度不一定等于这个数组的长度

而在实现add()函数的时候,这里简单的考虑了一下扩容。

具体实现的代码为:

import java.util.Arrays;

public class priQueue {

    private  int size;//优先队列的大小
    private  int capacity;//数组的容量
    private  int value[];//储存的值

    public priQueue() {
        this.capacity = 10;
        this.value = new int[capacity];
        this.size=0;
    }
    public priQueue(int capacity) {
        this.capacity = capacity;
        this.value = new int[capacity];
        this.size=0;
    }

    /**
     * 插入元素
     * @param number
     */
    public void add(int number) {
        if(size==capacity)//扩容
        {
            capacity*=1.5;
            value= Arrays.copyOf(value,capacity);
        }
        value[size++]=number;//先加到末尾
        int index=size-1;
        while (index>=1) {//进行交换
            if(value[index]<value[index/2]) {
                swap(index,index/2,value);
                index=index/2;
            }
            else//不需要交换即停止
                break;
        }
    }
    public int peek() {
        return  value[0];
    }

    /**
     * 抛出队头
     * @return
     */
    public int pop() {
        int val=value[0];//呆返回数据额
        value[0]=value[--size];//将最后一个元素赋值在堆头
        int index=0,leftChild=0,rightChild=0;
        while (true)
        {
            leftChild=index*2+1;
            rightChild=index*2+2;
            if(leftChild>=size)//左孩子必须满足在条件内
                break;
            else if(rightChild<size&&value[rightChild]<value[index]&&value[rightChild]<value[leftChild])
            {//右孩子更小
                swap(index,rightChild,value);
                index=rightChild;
            }
            else if(value[leftChild]<value[index])
            {//左孩子更小
                swap(index,leftChild,value);
                index=leftChild;
            }
            else //不需要 它自己最小
                break;
        }
        return  val;
    }
    //交换两个元素
    public  void swap(int i,int j,int arr[]) {
        int team=arr[i];
        arr[i]=arr[j];
        arr[j]=team;
    }

    public int size() {
        return  size;
    }
}

写个类测试一下看看:

在这里插入图片描述

结语

在这里插入图片描述

本次优先队列介绍就到这里啦,感觉不错记得点赞或一键三连哦,建议和堆排序一起看和学习效果更佳,要能够手写代码。个人公众号:bigsai 回复 bigsai 更多精彩和资源与你分享。
在这里插入图片描述

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
8480 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10287 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
2245 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
12151 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4549 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
6548 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
3651 0
+关注
bigsai
微信公众号「bigsai」白嫖电子书
22
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载