堆的简单实现

举报
兔老大 发表于 2021/04/23 01:38:19 2021/04/23
【摘要】 关于堆不做过多介绍 堆就是儿子的值一定不小于父亲的值并且树的节点都是按照从上到下,从左到右紧凑排列的树。 (本文为二叉堆) 具体实现并不需要指针二叉树,用数组储存并且利用公式找到父子即可。 父:(i-1)/2 子:i*2+1,i*2+2 插入:首先把新数字放到堆的末尾,也就是右下角,然后查看父的数值,需要交换就交换,重复上述操作直到不需交换 删除:把堆的第一个节...

关于堆不做过多介绍

堆就是儿子的值一定不小于父亲的值并且树的节点都是按照从上到下,从左到右紧凑排列的树。

(本文为二叉堆)

具体实现并不需要指针二叉树,用数组储存并且利用公式找到父子即可。

父:(i-1)/2

子:i*2+1,i*2+2

插入:首先把新数字放到堆的末尾,也就是右下角,然后查看父的数值,需要交换就交换,重复上述操作直到不需交换

删除:把堆的第一个节点赋值为最后一个节点的值,然后删除最后一个节点,不断向下交换。

(两个儿子:严格来说要选择数值较小的那一个)

时间复杂度:和深度成正比,所以n个节点是O(logN)


  
  1. int heap[MAX_N],sz=0;
  2. //定义数组和记录个数的变量

插入代码:


  
  1. void push(int x)
  2. {//节点编号
  3. int i=sz++;
  4. while(i>0)
  5. {
  6. int p=(i-1)/2;//父
  7. if(heap[p]<=x)break;//直到大小顺序正确跳出循环
  8. heap[i]=heap[p];//把父节点放下来
  9. i=p;
  10. }
  11. heap[i]=x;//最后把自己放上去
  12. }

弹出:


  
  1. int pop()
  2. {
  3. int ret=heap[0];//保存好值,最后返回
  4. int x=heap[--sz];
  5. while(i*2+1<sz)
  6. {
  7. int a=i*2+1;//左孩子
  8. int b=i*2+2;//右孩子
  9. if(b<sz && heap[b]<heap[a])a=b;//找最小
  10. if(heap[a]>=x)break;//直到不需要交换就退出
  11. heap[i]=heap[a];//把儿子放上来
  12. i=a;
  13. }
  14. head[i]=x;//下沉到正确位置
  15. return ret;//返回
  16. }

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/81706288

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200