浅浅理解一下堆

目录

一、堆的定义及本质

二、堆的核心操作

1、向下调整

2、堆的创建

3、向上调整

 三、堆的比较器传入及堆中简单函数的实现

四、堆的应用

1、用于OS调度进程

2、topk问题

 3、堆排序


一、堆的定义及本质

堆在Java中是以优先级队列来表现的(PrityQueue),不传入外部比较器则以小堆来实现(取出最小值)

前提:优先级队列中的元素具备比较能力(1.元素类型本身是可以比较的 2.通过构造方法传入一个外部比较器)

堆的作用:常用来在频繁变动的数据集中找出最值

堆的本质:逻辑上是完全二叉树,本质上是数组

堆的定义:

堆总是满足下列性质:

1.堆中某个节点的值总是不大于或不小于其父节点的值;

2、堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构,相当于一维数组,有两个直接后继。

 对于一个结点 2*index+1 是他的左节点 2*index+2是右节点   (index-1)/ 2 可以求得父节点

二、堆的核心操作

1、向下调整

当我们从堆顶取走一个最值时,这时堆的结构已经发生变化,我们往往用堆的最后一个结点来代替堆的根,但此时有可能这个值已经不满足堆的定义,我们需要对其进行向下调整,此时只有堆根部不满足堆的定义

 我们此时对根部进行调整

我们首先想到在根的左右结点中找到最小的值来判断是否大于根,如果根已经是最小值,则满足堆的定义,不需要进行交换,否则根与最小值进行交换

 //对堆的根部进行向下调整//结束调整的条件?  已经满足堆的结构,无需调整    当前结点已经是叶子结点,下边没有节点,无需调整public void justDown(int arr[],int size,int index){int left=2*index+1;//判断左子树是否存在,如果没有左子树,必没有右子树(完全二叉树性质)while (left<size){int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找出左右子树中的最小值int largest=arr[index]<=arr[min]?index:min;//在根和最小值中再找出最小值if (largest==index) break;//如果根就是最小值 堆结构已满足 退出循环swap(arr,index,min);  //不满足交换根和最小值,根等于最小值进行下一次调整index=min;left=index*2+1;}}private void swap(int[] arr, int index, int min) {int temp=arr[index];arr[index]=arr[min];arr[min]=temp;}

2、堆的创建

在我们已经掌握向下调整的情况下,如何将一个完全二叉树调整为堆呢?

我们可以对每个结点进行向下调整,使每个结点都满足堆的定义

但我们知道向下调整的结束条件是当前结点已经满足堆的结构或者当前结点是叶子结点,因此我们没有必要对叶子结点进行调整,而在完全二叉树中我们很容易找到最后一个结点(size-1)是最后一个结点的下标 而他的父节点是(size-1-1)/ 2   那么自他的父节点之后就全是叶子节点

public void creatHeap(int[] arr,int size){for (int i=(size-2)/2;i>=0;i--){justDown(arr,size,i);}}

为什么从上到下不行?因为我们向下调整是由要求的,必须左右子树已经是一个堆结构了 如果不理解可以画图。。

 

在经历一次向下调整时我们发现最小的1永远没有走到顶部的机会,为什么呢,因为我们没有满足向下调整的定义。没有找到真正最小的那个数调整到堆顶 

3、向上调整

在我们创建完成一个堆的时候,往往需要往堆里边添加新的元素,由于我们从数组【0,size)是已经创建好的堆结构,在我们新添加一个元素时,往往需要向上调整

public void justUp(int[] arr,int index){int parent=(index-1)/2;//父节点下标while (arr[index]>arr[parent]){//当子节点大于父节点时我们需要向上调整swap(arr,index,parent);index=parent;//新的Index是他的父节点parent=(index-1)/2;//新的parent结点}}

 三、堆的比较器传入及堆中简单函数的实现

假设当前有一个person类,里边的属性有姓名和年龄,此时person是默认不支持比较的

 public class person{String name;int age;}

在不修改person类的情况下我们如何实现比较年龄呢?

答案是采用外部比较器

static class PersonComparator implements Comparator<Person>{@Overridepublic int compare(Person o1, Person o2) {return o1.age-o2.age;}}
 static class PersonComparator implements Comparator<Person>{@Overridepublic int compare(Person o1, Person o2) {return o1.age-o2.age;}}public static void main(String[] args) {PriorityQueue<Person> pq=new PriorityQueue(new PersonComparator());pq.add(new Person("小明",11));pq.add(new Person("小红花",9));pq.add(new Person("小刚",21));while (!pq.isEmpty()){System.out.println(pq.poll().toString());}}

堆的简单函数全实现:

public class MyPriorityQueue{long arr[];int size;public MyPriorityQueue(){//由于我们的元素类型是long类型没有采用泛型,所以不涉及传入比较器arr=new long[20];size=0;}public void add(long val){//往堆中加入一个元素ensureCapacity();//保证数组空间够用arr[size]=val;justUp(arr,size);//新加入的元素需要向上调整维持一个堆结构size++;}public long peek(){//查看堆顶部元素if (size<0){throw new RuntimeException("队列是空的");}return arr[0];}public long poll(){//弹出堆顶部的元素if (size<0){throw new RuntimeException("队列是空的");}long res=arr[0];//先记录需要返回的元素arr[0]=arr[size-1];//把最后一个元素调整到堆的顶部并向下调整arr[size-1]=0;//最后一个元素交换到堆顶,那么它就要改为默认值size--;justDown(arr,size,0);return res;}public int size(){return size;}private void justDown(long[] arr, int size, int index) {int left=index*2+1;while (left<size){//如果还有子节点(不是叶子节点)int min=left+1<size&&arr[left+1]<arr[left]?left+1:left;//找到左右子结点中的最小值int largest=arr[min]<arr[index]?min:index;//找到最小的值if (largest==index) break;//如果index本身就是最小值说明他已经满足堆结构不需要调整swap(arr,min,index);//交换index和最小值index=min;//新的indexleft=index*2+1;//新的最小值}}public void check(){//检查是否满足堆结构if (size<0||size>arr.length){throw new RuntimeException("size越界");}for (int i=0;i<size;i++){int left = 2 * i + 1;int right = 2 * i + 2;if (left >= size) {// 说明是叶子,跳过continue;}// 左孩子破坏了规则if (arr[i] > arr[left]) {throw new RuntimeException(String.format("[%d] 位置的值大于其左孩子的值了", i));}// 右孩子破坏了规则if (right < size && arr[i] > arr[right]) {throw new RuntimeException(String.format("[%d] 位置的值大于其右孩子的值了", i));}}}private void justUp(long[] arr, int index) {while (index!=0){int parent=(index-1)/2;if (arr[parent]<=arr[index]) return;swap(arr,index,parent);index=parent;}}public boolean isEmpty(){return size==0;}private void ensureCapacity() {if (size<arr.length) return;arr= Arrays.copyOf(arr,size*2);}public void swap(long[] arr,int i,int j){long temp=arr[i];arr[i]=arr[j];arr[j]=temp;}
}

四、堆的应用

1、用于OS调度进程

2、topk问题

topk问题其实在现实生活有很多场景,比如说淘宝的好物top10等等

假如说我们要在很多数据中找到前k个最大的数  我们有什么思路呢?

1.对所有的数据进行排序再取出前十

这种方法无疑消耗的时间成本和空间成本是是非常高的

时间复杂度达到了O(N*logN) 空间复杂度是O(N)

2.把所有的数据入堆,在取出前k个元素 

第二种方法的时间复杂度相较于第一种减少了很多 大概是O(k*logN),但我们忽略了在数据非常庞大时,堆的向下调整操作往往也需要耗费大量时间,并且空间复杂度也达到了惊人的O(N)

3.我们采用建小堆,小堆的size就是k,如果当前元素比小堆中最小元素大,我们就把它加进去,到最后堆里的元素就是topk

并且空间复杂度也只有O(k)

代码如下:

public class Solution {public int[] smallestK(int[] arr, int k) {if (k==0){ //处理特殊情况,防止堆为空造成的index越界return new int[0];}PriorityQueue<Integer> pq=new PriorityQueue<>(((o1, o2) -> o2-o1));for (int i=0;i<k;i++){ //添加k个元素进入堆pq.add(arr[i]);}for (int i=k;i<arr.length;i++){//维持堆中的元素是最小的k个if (arr[i]<pq.peek()){pq.poll();pq.add(arr[i]);}}int[] res=new int[k];//返回这k个元素int i=0;while (!pq.isEmpty()){res[i++]=pq.poll();}return res;}
}

 3、堆排序

堆排序是一种利用堆结构找到最值然后不断取出进行排序,本质上是一种选择排序,不过由于堆找出并维持最值的时间复杂度是O(N*longN)所以他是一种高效的排序

我们把需要排序的数组看  无序加有序的形式 一旦我们找到最值元素 我们就把它交换到最后边

因此总的排序要进行arr.length-1次交换

public void swap(long[] arr,int i,int j){long temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public long[] heapSort(long[] nums){//首先我们需要建立大堆,把大的元素找出并交换到最后边buildHeap(nums);for (int i=0;i<nums.length-1;i++){swap(nums,0,arr.length-1-i);justDown(nums,arr.length-i-1,0);}return nums;}private void buildHeap(long[] nums) {for (int i=(nums.length-2)/2;i>=0;i--){justDown(nums,nums.length,i);}}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/30768.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

浅浅的复习一下sql

DISTINCT 语法&#xff1a; SELECT DISTINCT 列名称 FROM 表名称1、现在有一个表如下&#xff1a; 2、执行sql语句-1 SELECT DISTINCT ename,email FROM emp 结果&#xff1a; 说明&#xff1a;由于小刘的ename和email重复了&#xff0c;所以结果只显示一次&#xff01; 3…

浅浅仿制一个APP首页

一、实验目标 做一个APP首页&#xff0c;包括顶部图片、顶部菜单栏、中部消息模块、底部Tab按钮。学习 ScrollView, RelativeLayout&#xff0c;以及插件之间的穿插使用。 二、实验步骤 列出实验的关键步骤、代码解析、截图。 1.逻辑梳理 做一个app首页&#xff0c;包括顶部…

花嫁之容氏浅浅最后怎么样了_花嫁之容氏浅浅章节目录阅读

花嫁之容氏浅浅小说完整版无弹窗在线阅读。花嫁之容氏浅浅小说是作者&#xff1a;许暖暖创作完成的一本热门玄幻灵异小说&#xff0c;主要讲述女主舒浅和鬼王容祁两人的精彩故事。梦里&#xff0c;舒浅感受到一双冰冷的手在自己身上游走&#xff0c;可是即使这样&#xff0c;舒…

干货文章 | 低代码真的有价值吗?

作者&#xff1a;瀚码技术钟惟渊&#xff08;第⼀作者&#xff09;、独⽴顾问王甲佳&#xff08;第⼆作者&#xff09;、瀚码⼀⼑云叨叨AI助⼿&#xff08;第三作者&#xff09; 全文共4912字&#xff0c;阅读约需要15min 本系列文章由瀚码技术钟惟渊构思、制定大纲、组织了关…

零信任落地实践【新世界】

&#x1f315;写在前面 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; ✉️今日分享&#xff1a; 莫道前路多险阻&#xff0c;再闯关山千万重 &#x1f340; 前言 轻舟已过万重山&#xff0c;始终不忘初心。在网络安全领域&#xff0c;我们…

神龙显灵-走进中国传统节日二月二龙抬头

二月二龙抬头&#xff0c;是中国传统的节日之一&#xff0c;也是春节的收官之战。这个节日被视为一个转折点&#xff0c;标志着春天的到来&#xff0c;也为农民们带来了新的希望和期待。 二月二这个日子有很多习俗和传说&#xff0c;其中最著名的就是“龙抬头”。据传说&#…

盘古大模型,让人人实现数字人自由

编辑&#xff1a;阿冒 设计&#xff1a;沐由 就在华为开发者大会2023 < HDC.Cloud 2023 > 正式开启的前夜&#xff0c;一则重磅消息从海外传来&#xff1a; 国际顶级学术期刊《自然》&#xff08;Nature&#xff09;杂志正刊发表了华为云盘古大模型研发团队研究成果——《…

奥运礼服设计师:AIGC 让童装设计从绿皮车进入高铁时代

近日&#xff0c;由温州 AIGC 产业联盟、温州市服装商会共同发起的“首届温州鞋服产业 AIGC 设计大赛”活动正如火如荼进行。大赛聚焦 13 岁青少年服饰设计这一行业存在已久的难题&#xff0c;探讨如何利用 AIGC 热门工具解决青少年服装设计痛点。据巴比特了解&#xff0c;该活…

每日互动(个推)CTO叶新江:AIGC时代,大模型推动数据要素商业化

ChatGPT在一夜之间火爆互联网&#xff0c;让AIGC受到世界范围内的高度关注。时至今日&#xff0c;AIGC热度持续高涨&#xff0c;各大互联网公司争相布局这一领域。日渐成熟的技术、显著的降本增效优势以及日益增长的市场需求等因素&#xff0c;已经推动AIGC成为互联网公司新一轮…

YEF 2023 18日开幕,逾千青年精英齐聚话“突围”

YEF2023 18日在温州开幕&#xff0c;在CCF YOCSEF创建25周年之际&#xff0c;逾千名计算机相关的学术、技术、产业、媒体、社会组织中的青年人才&#xff0c;汇聚温州鹿城区&#xff0c;一起回望、一起思辨、一起突围。 5月18日上午&#xff0c;由CCF主办&#xff0c;温州市人民…

AI大模型迈入应用时代,每日互动推动“可控大模型”落地

垂直行业更需要可控大模型 当下&#xff0c;大模型正在不断精进&#xff0c;以GPT-4、文心一言为代表的大模型&#xff08;LLM&#xff09;表现出了强大的逻辑推理能力&#xff0c;并能够很好地处理复杂任务&#xff0c;使得社会生产力得到了飞跃式提升。 面对大模型热度的持…

喜报 | 客户赞誉!获温州银行授予优秀供应商证书

近日&#xff0c;温州银行金融科技部在杭州、温州两地同时展开2022年度供应商表彰活动&#xff0c;意在鼓励先进、鼓舞干劲。擎创科技作为温州银行长期合作的供应商之一&#xff0c;凭借在智能运维领域精研的技术优势及“以客户成功为本”的服务价值观&#xff0c;深得客户青睐…

数画自研chatgpt,imagegpt人工智能语言技术,颠覆对AI绘画的认知

2023年1月1日&#xff0c;数画AI绘画又爆火了&#xff0c;这一次是数画团队自研了chatGPTimageGPT人工智能技术&#xff0c;值得人们注意的是&#xff0c;并非引用海外的openAI人工智能语言模型&#xff0c;而是完全自研首发的国产人工智能技术&#xff0c;数画团队来自于温州专…

使用SVG.Net生成svg格式文字图片

由于项目需要&#xff0c;需生成svg格式文字图片&#xff0c;网上的文档较少&#xff0c;在一番查阅之后成功实现。现记录下来&#xff0c;方便以后自己查阅&#xff0c;以及需要的人也可当做参考&#xff0c;水平不高&#xff0c;少喷。 主要运用到GitHub开源项目: svg.net 不…

利用ps导出svg(主要用于上传自定义图标到iconfont)

ps版本&#xff1a;2020 借鉴文章&#xff1a;https://blog.csdn.net/k912120/article/details/118787809 事情起因是我不想多此一举下个AI,本来想ps直接导出svg格式,但是导出来上传到iconfont后却是一片空白&#xff0c;相信很多人第一次都遇到过这种情况。 我一愣&#xff…

将图片转化成SVG格式(亲测可行)

1.准备好要转化的图片 可以看到左侧图片是一个jpg格式的&#xff0c;接下来我们就把它转化成svg格式; 2.打开SVG在线编辑器&#xff0c;把图片导入 我们可以打开SVG在线编辑器&#xff0c;在SVG编辑器中导入图片并根据我们需要的大小进行设置&#xff0c;如下图&#xff1a; …

微信图文消息中如何使用svg图片

微信图文消息无法上传svg格式图片,但是可以通过浏览器开发者工具进行hack 将svg图片使用文本编辑器打开,复制内容登录微信公众平台,新建图文消息输入正文的输入框中输入随意文字打开浏览器控制台(右键检查或按F12),找到步骤2输入文字对应的html标签在html标签右键,选择’Edit …

原腾讯QQ技术总监、T13专家,黄希彤被裁,原因竟是不愿意被 PUA ?

整理 | 朱珂欣 出品 | CSDN程序人生&#xff08;ID&#xff1a;coder_life&#xff09; 曾经风光无限的互联网“淘金地”&#xff0c;为无数技术人提供了造梦机会&#xff0c;也带领着一批程序员走向致富之路。然而&#xff0c;如今国内各大厂也在经历着“瘦身”运动。 据 T…

被裁后,前 Google 工程师揭露:Google Brain 没落的真实原因!

【CSDN 编者按】一周之前&#xff0c;为了更好地追赶 OpenAI&#xff0c;Google 做了一个重大的决定&#xff1a;Brain 和 Deepmind 合并&#xff0c;这件事引得很多人的关注与不解。最近波及其中的 Google Brain 高级工程师 Brian Kihoon Lee 于上周被解雇&#xff0c;他毕业于…

Meta 计划最快本周裁员数千人,网友:工作不易,且行且珍惜!

【CSDN 编者按】新的一轮裁员风波来袭&#xff0c;Meta 计划最快在本周再裁员数千人。 整理 | 王子彧 出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09; 伴随着 ChatGPT 的火爆出圈&#xff0c;AI 取代一些普通员工的讨论还没中止之际&#xff0c;各大企业的裁员举措…